Let $N$ be a positive integer. Define a sequence $a_0,a_1,\ldots$ by $a_0=0$, $a_1=1$, and $a_{n+1}+a_{n-1}=a_n(2-1/N)$ for $n\ge1$. Prove that $a_n<\sqrt{N+1}$ for all $n$. Evan O'Dorney.
Problem
Source: ELMO Shortlist 2011, A3
Tags: induction, complex numbers, imaginary numbers, algebra proposed, algebra
math154
03.12.2012 07:55
Sorry, I originally typoed "$a_0=1$" but it's now fixed (should be $a_0=0$). Hopefully I didn't miss any other small but important things like this.
Rust
03.12.2012 11:15
$a_n=Re(\frac{i}{\sqrt{1-\alpha^2}}x^n)$, were $x=\alpha-i\sqrt{1-\alpha^2}, \alpha=1-\frac{1}{2N}$. Therefore $|a_n|<\frac{2N}{\sqrt{4N-1}}<\sqrt{N+c}$ if $(4c-1)N-c\ge 0$. It is true for $c\ge \frac 13$. It mean $|a_n|<\sqrt{N+\frac 13}.$
Wolstenholme
29.07.2014 02:37
Since Rust's post is in my opinion difficult to understand, I will post a complete solution. Let $ a = 2 - \frac{1}{N} $. Then our recurrence has characteristic equation $ x^2 - ax + 1 = 0 $ which has roots $ \frac{a \pm \sqrt{a^2 - 4}}{2} $. It is well-known that the closed form for $ a_n $ is given by: $ a_n = c_{1}\left(\frac{a + \sqrt{a^2 - 4}}{2}\right)^n + c_{2}\left(\frac{a - \sqrt{a^2 - 4}}{2}\right)^n $ for some real $ c_1, c_2 $. Using the given fact that $ a_0 = 0 $ and $ a_1 = 1 $ we quickly find that $ c_1 = \frac{1}{\sqrt{a^2 - 4}} $ and $ c_2 = \frac{-1}{\sqrt{a^2 - 4}} $. Now since $ \sqrt{a^2 - 4} $ is an imaginary number we find that $ a_n = \frac{2}{\sqrt{4 - a^2}} \cdot Im{\left(\frac{a + \sqrt{a^2 - 4}}{2}\right)^n} $. Re-substituting $ a = 2 - \frac{1}{N} $ this becomes $ a_n = \frac{2N}{\sqrt{4N - 1}} \cdot Im{\left(\left(1 - \frac{1}{N}\right) + \frac{\sqrt{4N - 1}}{2N}i\right)^n }$. Because $ \left(1 - \frac{1}{N}\right)^2 + \left(\frac{\sqrt{4N - 1}}{2N}\right)^2 = \frac{4N^2 - 4N + 3}{4N^2} < 1 $ we have that $ Im{\left(\left(1 - \frac{1}{N}\right) + \frac{\sqrt{4N - 1}}{2N}i\right)^n < 1 }$ for all positive integers $ n $. Therefore $ a_n < \frac{2N}{\sqrt{4N - 1}} $ for all positive integers $ n $. So it suffices to show that $ \frac{2N}{\sqrt{4N - 1}} \leq \sqrt{N + 1} $ which is trivial. The motivation behind this solution is that linear recurrences such as these easily lend themselves to closed forms (which can be rigorously proven to hold through induction or generating functions). Once a closed form is obtained dealing with powers of complex numbers is difficult and so it is natural to consider magnitudes instead.
Ankoganit
11.09.2016 18:43
Assuming I did not mess up the inequality signs, the following solution is not at all complex (pun intended). Edit: Aaaand I did mess up. I'll try to patch it up; for now ignore the "solution" below.
If $a_{n}<a_{n-1}$ for some $n$, then $a_{n+1}=\left(2-\frac 1N\right)a_n-a_{n-1}<2a_n-a_{n-1}<a_n$. So if the sequence $\langle a_i\rangle$ decreases at some point, it decreases ever after. Contrapositively, if $\langle a_i\rangle$ is increasing upto some point, then it must have been increasing ever before.
Also, we notice that the given equation may be written as $(a_{n+1}-a_n)=(a_n-a_{n-1})-\frac{a_n}{N}$, so applying this over and over again, we have
\begin{align*} a_{n+1}-a_n=& (a_n-a_{n-1})-\frac{a_n}{N}\\
=&(a_{n-1}-a_{n-2})-\frac{a_{n-1}}{N}-\frac{a_n}{N}\\
\vdots &\\
=&(a_1-a_0)-\frac{a_1+a_2+\cdots +a_n}{N}\\
\implies a_{n+1}=&1+a_n-\frac{a_1+a_2+\cdots +a_n}{N} & (1)\\
=&1+\frac{(a_n-a_1)+(a_n-a_2)+\cdots +(a_n-a_n)}{N} & (2)\end{align*}
If $\langle a_i\rangle$ is increasing all the way upto $a_N$, i.e., if $a_N\ge a_{N-1}\ge\cdots\ge a_1=1$, then setting $n=N$ in $(1)$ gives $$ a_{N+1}-a_N=1-\frac{\displaystyle\sum_{i=1}^{N}a_i}{N}< 1-\frac{\displaystyle\sum_{i=1}^{N}a_1}{N}=1-\frac{N}{N}=0.$$So $\langle a_i\rangle$ decreases past that point. This means we only need to worry about $n\le N$.
Now let us induct on $n$. The base case is trivial. Assume $a_1,a_2,\cdots ,a_n<\sqrt{N+1}$. If $a_{n+1}\le a_n$, then we were immediately done. Otherwise, if $a_{n+1}>a_n$, then the first paragraph implies $a_1<a_2<\cdots <a_n$. So from $(2)$,
\begin{align*} a_{n+1}=& 1+\frac{(a_n-a_1)+(a_n-a_2)+\cdots +(a_n-a_n)}{N}\\
<& 1+\frac{(a_n-a_1)+(a_n-a_1)+\cdots +(a_n-a_1)}{N}\\
<& 1+\frac{n\left(\sqrt{N+1}-1\right)}{N}\le 1+(\sqrt{N+1}-1) \quad\text{[Because }n\le N]\\
=&\sqrt{N+1}\end{align*}
This completes our induction, and hence also the proof. $\blacksquare$