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
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.
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}.$
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.
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.