M 3

Art of Problem Solving

AoPS Online

PEN Math problems from the collection "Problems in Elementary Number Theory"

Math problems from the collection "Problems in Elementary Number Theory"

3 M G

BBookmark VNew Topic kLocked

PEN Math problems from the collection "Problems in Elementary Number Theory"

Math problems from the collection "Problems in Elementary Number Theory"

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

M 3

G H J

Reveal topic tags

Recursive Sequences

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3615 posts

Peter

#1 h May 25, 2007, 12:25 AM • 2 Y

Y by Adventure10, Mango247

Let $f(n)=n+\lfloor \sqrt{n}\rfloor$ . Prove that, for every positive integer $m$ , the sequence $m, f(m), f(f(m)), f(f(f(m))), \cdots$ contains at least one square of an integer.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1677 posts

#2 h Sep 15, 2007, 3:03 AM • 1 Y

Y by Adventure10

Induct on $m$ . The case $m = 1$ is trivial. Now prove true for $m$ given true for $m-1$ .

For all positive integers $x > 1$ , $f(x)-f(x-1)$ equals 2 when $x$ is a square and 1 otherwise. Suppose that the sequence $f^{n}(m)$ does not contain a square. It then follows that $f^{n}(m)-f^{n}(m-1) = 1$ for all $n$ . Now there exists $N$ such that $f^{N}(m-1) = a^{2}$ for some positive integer $a$ . We then get
$f^{N+1}(m-1)=a^{2}+a,\ f^{N+2}(m-1)=a^{2}+2a,$

$f^{N+2}(m)=a^{2}+2a+1=(a+1)^{2}$
a contradiction, as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

49 posts

Woett

#3 h Feb 16, 2011, 3:15 AM • 1 Y

Y by Adventure10

Largely empirically I found the following facts (see what you can prove and note that all letters denote positive integers, unless stated otherwise):

1) The base units for the sequence $m, f(m), f(f(m)), ..$ are such that $m = n^2 + n - 1$ . That is, if $m$ is not of that form, it occurs somewhere in the sequence $f(m'), f(f(m')), ..$ for some $m'$ smaller than $m$ . So we can focus our attention on those base units; set $m = n^2 + n - 1$ for the remainder.
2) The smallest $x$ such that $x^2$ occurs in the sequence is equal to $2n - 1$ and occurs after $2n - 2$ steps; $f^{2n-2}(m) = (2n - 1)^2 = x^2$
3) $y^2$ occurs in the sequence if, and only if, $y = x2^l$ for some $l \ge 0$
4) If $f^k(m) = 4^lx^2$ , then $f^{2k+2n+1-l}(m) = 4^{l+1}x^2$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a