I think there is no such sequence. First of all if it exists then it is increasing. Let $x_n^2=a_{n+1}+a_n,$ then from $a_{n+2}-a_{n+1}=x_n$ and $a_{n+2}+a_{n+1}=x_{n+1}^2$ we get $a_{n+2}=\frac{1}{2}(x_n+x_{n+1}^2)$ and $a_{n+1}=\frac{1}{2}(x_{n+1}^2-x_n)$ thus by replacing $n$ by $n+1$ we get $x_{n+2}^2-x_{n+1}^2=x_{n+1}+x_n$ thus $\prod_{i=1}^n (x_{k+2}-x_{k+1})=\frac{x_2+x_1}{x_{n+2}+x_{n+1}}<1$ which it is a contradiction since the sequence of integers $(x_n)$ is strictly increasing.

We can also use $x_n=a_{n+1}-a_n\geq 1$ and that $a_n\to \infty...$

I'm probably very stupidly messing up somewhere, but can't we just do this?

my solution = we claim that there exist no such sequence obviously the given sequence is increasing. now we have $a_{n+2}^2+a_{n+1}^2-2a_{n+1}{n+2}=a_{n+1}+a_{n}$ or $(a_{n+2} - a_{n})(a_{n+2}+a_{n} - 2a_{n+1})=a_{n+1} - a_{n-1}>0$ and thus $a_{n+2} - a_{n+1}\ge a_{n+1} - a_{n}$ and hence is increasing for all $n$. also $a_{n+2} - a_{n-1}\le a_{n+1} - a_{n-1}$ so its a decreasing sequence for all $n$ but than $a_{n+1} - a_{n-1} = a_{n+1} - a_{n} +a_{n} - a_{n-1} $ is a increasing sequence for all $n$ and hence a contradiction! and thus we prove our claim so we are done !

randomusername wrote:

nice solution!

is this problem comparable to a IMO N1?? how much does it rate on terms of Olympiad difficulty??

aditya21 wrote: Determine whether there exists an infinite sequence $a_1, a_2, a_3, \dots$ of positive integers which satisfies the equality \[a_{n+2}=a_{n+1}+\sqrt{a_{n+1}+a_{n}} \] for every positive integer n. Let $x_n = a_{n+1}-a_n = \sqrt{a_{n}+a_{n-1}}$; since the $(a_n)$ are strictly increasing for $n \ge 2$ so are the $(x_n)$ when $n \ge 3$. For $n \ge 2$ observe that \[ x_{n+1}^2 - x_n^2 = a_{n+1} - a_{n-1} = \left( a_{n+1}-a_{n} \right) + \left( a_{n}-a_{n-1} \right) = x_n + x_{n-1} \] or \[ 1 \le x_{n+1}-x_n = \frac{x_n+x_{n-1}}{x_{n+1}+x_n} < 1. \] This is a contradiction even at $n=4$ due to the increasing condition. . . it does not appear you can get the sequence $(a_n)$ to even have six terms, much less infinitely many terms. EDIT: As pointed out, I messed up some indices; thanks mavropnevma for the correction.

v_Enhance wrote: aditya21 wrote: Determine whether there exists an infinite sequence $a_1, a_2, a_3, \dots$ of positive integers which satisfies the equality \[a_{n+2}=a_{n+1}+\sqrt{a_{n+1}+a_{n}} \] for every positive integer n. Let $x_n = a_{n+1}-a_n = \sqrt{a_{n}+a_{n-1}}$; since the $(a_n)$ are strictly increasing so are the $(x_n)$. For $n \ge 2$ observe that \[ x_{n+1}^2 - x_n^2 = a_{n+1} - a_{n-1} = \left( a_{n+1}-a_{n} \right) + \left( a_{n}-a_{n-1} \right) = x_n + x_{n-1} \] or \[ 1 \le x_{n+1}-x_n = \frac{x_n+x_{n-1}}{x_{n+1}+x_n} < 1. \] This is a contradiction even at $n=2$. . . it does not appear you can get the sequence $(a_n)$ to even have five terms, much less infinitely many terms. probably the best solution and the shortest too!

v_Enhance wrote: This is a contradiction even at $n=2$. . . it does not appear you can get the sequence $(a_n)$ to even have five terms, much less infinitely many terms. In fact we can, for example $(a_1,a_2,a_3,a_4,a_5) = (477,7,29,35,43)$, but we cannot have six (positive integer) terms (you probably made a benign error in "reading" the indices). A major weakness of the problem (one would expect one can build as large a number of terms as one wants, but not infinitely many).

I was wrong.

mssmath wrote: The example given is definitely wrong as $a_n$ is strictly increasing. This example is totally correct ! the sequence is strictly increasing for $n \geq 2$ so that $a_2 <a_3< \cdots$

$a_{n+1} > a_n$ so the sequence is strictly increasing. Let $a_n +a_{n-1} = v^2$ and $a_{n-1} +a_{n-2} = u^2$. Since the sequence is strictly increasing, $v>u$. Then $a_{n+1} = a_n + v$ and $a_n = a_{n-1} + u$. Moreover $v^2=2a_{n-1}+u$. So $$v^2<a_{n+1}+a_n = 2a_n +v =2a_{n-1} +2u +v = v^2 +v+u < v^2 +2v < (v+1)^2$$Hence $a_{n+1}+a_n$ is not a perfect square. So no such sequence exists.

We can rearrange some terms from our original equation $(a_{n+2} - a_{n+1})^2 = a_{n+1} + a_n$ Now let $s^2_n = a_{n+1} + a_n$, then we can observe that $s_n = a_{n+2} - a_{n+1}$ so $a_n$ is a decreasing sequence However this is a contradiction because an infinite sequence will not exist, so we are done!

nevermind

aditya21 wrote: Determine whether there exists an infinite sequence $a_1, a_2, a_3, \dots$ of positive integers which satisfies the equality \[a_{n+2}=a_{n+1}+\sqrt{a_{n+1}+a_{n}} \]for every positive integer $n$. If we work on it with a recursive overview , then we get a quadratic recurrence relation which takes us to a dead end. An alternate approach follows

Similar to above solutions but for storage: No, there does not exist such a sequence. Suppose FTSOC that it did. First, see that the sequence of $a_i$ is strictly increasing. Then, let $a_i + a_{i+1} = x_i^2$. Obviously, $x_i$ is also strictly increasing. Now, $x_{n+1}^2 = a_{n+1} + a_{n+2} = a_{n+1} + (a_{n+1} + \sqrt{a_n + a_{n+1}}) = a_{n+1} + x_n + a_{n+1}$ $= a_{n+1} + x_n + (a_n + x_{n-1}) = a_n + a_{n+1} + x_n + x_{n-1} = x_n^2 + x_n + x_{n-1} > x_n^2 + 2x_n$ So, $x_n^2 < x_{n+1}^2 < (x_n+1)^2$, which is impossible

Probably wrong but still Note that $a_3=a_2+\sqrt{a_2+a_1}$. Let $a_2+a_1=k_1^2, k_1 \in \mathbb{N} \implies a_2=k_1^2-a_1$. We get $a_3=k_1^2 +k_1-a_1$. Now we must have $a_3=k_2^2-a_2, k_2 \in \mathbb{N}$. $$\implies a_3=k_2^2-a_2=k_2^2-k_1^2+a_1= k_1^2+k_1-a_1$$$$\implies 2a_1=2k_1^2+k_1-k_2^2$$Also, $$a_2=\frac{k_2^2-k_1}{2}$$and $$a_3=\frac{k_2^2+k_1}{2}$$Now, $$a_4=a_3+k_2=\frac{k_2^2+k_1}{2}+k_2$$We must have $a_3+a_4 = k_2^2+k_1+k_2 =\text{perfect square} \geq k_2^2+2k_2+1$ $$\implies k_1 \geq k_2+1 \implies a_1 > a_3$$. Now, one could continue this forever, replacing $1$ by $3$ in the first step and so on, and we get $a_1>a_3> \dots$ (Do this for $(a_3,a_4,a_5), \dots$ which isn’t possible if $n$ is infinitely big.

aditya21 wrote: Determine whether there exists an infinite sequence $a_1, a_2, a_3, \dots$ of positive integers which satisfies the equality \[a_{n+2}=a_{n+1}+\sqrt{a_{n+1}+a_{n}} \]for every positive integer $n$. $$a_n+a_{n+1}=(x_n)^2$$$$a_{n+2}=a_{n+1}+x_n$$$$a_{n+2}+a_{n+1}=(x_{n+1})^2$$$$(x_{n+1})^2=(x_n)^2+x_n+x_{n-1} \geq (x_n)^2+2x_n+1$$$$x_{n-1} \ge x_n +1$$Contradiction

Solved with Dimath27 Let $a_{n+1}-a_n=b_n$ then we have $b_{n+1}^2 = a_{n+1}+a_n$ (So $b_{n+1}>0$) then $b_{n+2}^2 = a_{n+2}+a_{n+1}$ so subtracting both equations: $$b_{n+2}^2 - b_{n+1}^2=a_{n+2}-a_n = b_n + b_{n+1} $$ This implies that $\{b_n\}$ is increasing but: $b_n + b_{n+1} = b_{n+2}^2 - b_{n+1}^2 = (b_{n+2} + b_{n+1})(b_{n+2}-b_{n+1}) \ge b_{n+2} + b_{n+1} > b_n + b_{n+1}$ !Contradicction¡ So there is no such sequence. $\blacksquare$

it is easy to see $a_{i} + a_{i+1}$ is perfect square . Now we can see our sequence is strictly ascending . $$a_{n+2} < a_{n+1}+\sqrt{2a_{n+1}} $$and $$a_{n+1} < a_{n}+\sqrt{2a_{n}} $$ Then $a_{n}+a_{n+1} < a_{n+2}+a_{n+1} <a_{n+1}+\sqrt{2a_{n+1}}+a_{n}+\sqrt{2a_{n}}$ Also we know $\sqrt{2a_{n+1}}+\sqrt{2a_{n}} \leq 2\sqrt{a_{n}+a_{n+1}}$ . Now a perfect square phrase is between two consecutive perfect square .

The answer is $N=5$. For a construction, we can use $(477, 7, 29, 35, 43)$. To prove that this is maximal, assume for the sake of contradiction that $N \geq 6$. Then, define $a_i+a_{i+1} = k_i^2$ for all $1 \leq i \leq 4$; because $a_6$ is an integer, all the $k_i$ must also be integres. Now, we have \begin{align*} a_3-a_2 &= k_1 \\ a_2+a_3 &= k_2^2 \end{align*}so $a_3 = \frac{k_2^2+k_1}2 = \frac{k_3^2-k_2}2$ by solving the same system for $a_3, a_4$. Thus, \begin{align*} k_3^2 - k_2^2 &= k_1+k_2 \\ k_4^2 - k_3^2 &= k_2+k_3 \end{align*}where the second equation follows similarly. But it is clear that $k_2 < k_3 < k_4$, so $$k_2+k_3 < k_4+k_3 \leq k_4^2 - k_3^2,$$contradiction.

The answer is $N=\boxed{5}$. The construction is $(477, 7, 29, 35, 43)$. Now, we will show that $5$ is the upper bound. Assume that $N = 6$. If we can obtain a contradiction, then it will be impossible to construct a sequence with more than $6$ terms. Let $a_1=a$, $a_2=b$, and denote $s=\sqrt{a+b}$ to simplify. After applying the recursive formula multiple times, we get \[a_6=b+s+\sqrt{2b+s}+\sqrt{2b+2s+\sqrt{2b+s}}+\sqrt{2b+2s+2\sqrt{2b+s}+\sqrt{2b+2s+\sqrt{2b+s}}}\] We let $x=\sqrt{2b+2s+\sqrt{2b+s}}$ and $y=\sqrt{2b+s}$. Then, \[a_6=b+s+x+y+\sqrt{x^2+x+y}\] so $x^2+x+y$ must be a perfect square. However, $x>y$ so \[x^2<x^2+x+y<x^2+2x+1=(x+1)^2\] so $x^2+x+y$ cannot be a perfect square, a contradiction. Thus, $N \ge 6$ is impossible, proving our upper bound.

From the recursion, we get that \[a_{2} < a_{3} < a_{4} <\cdots \implies a_{2}+a_{3} < a_{3}+a_{4} < a_{4}+a_{5} <\cdots\]Note that \[a_{n+2}+a_{n+1} = a_{n+1}+a_{n} + \sqrt{a_n+a_{n+1}}+\sqrt{a_{n}+a_{n-1}}\]Let $a_{k}+a_{k+1} = b_{k}^2$. Then, we have that \begin{align*} (b_{3} -b_{2})(b_{3}+b_{2}) &= b_{2}+b_{1} \\ (b_{4} -b_{3})(b_{4}+b_{3}) &= b_{3}+b_{2} \\ \cdots \\ (b_{N-1}-b_{N-2})(b_{N-1}+b_{N-2}) &= b_{N-2}+b_{N-3} \end{align*}Note that $b_{2} < b_{4} \implies b_{4}-b_{3} = \frac{b_{3}+b_{2}}{b_{4}+b_{3}} < 1$. This means that $b_{4}$ can't be an integer, implying that $N = 5$ is the maximum. Note that $(477, 7, 29, 35, 43)$ satisfies this maximum.

Let $b_n=\sqrt{a_{n+1}+a_n}=a_{n+2}-a_{n+1}.$ Then we have that $$b_n+b_{n+1}^2=2a_{n+2}=2b_n+2a_{n+1} = 2b_n+b_{n-1}+b_n^2 \implies b_{n+1}^2-b_n^2=b_n+b_{n-1} \implies b_{n+1}-b_n = \frac{b_n+b_{n-1}}{b_n+b_{n+1}}.$$However, not that $a_n$ is strictly increasing, meaning that $b_n$ is too so $$b_{n+1}-b_n <1,$$a contradiction because $b_n$ is a strictly increasing sequence of integers. However, this proof relies on the fact that $N \geq 6,$ meaning that $N \leq 5.$ A valid construction to this would be $(477, 7, 29, 35, 43).$