Problem

Source: ELMO Shortlist 2011, A3

Tags: induction, complex numbers, imaginary numbers, algebra proposed, algebra



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.