Putnam 2007, Problem B-3

Let $x_0 = 1$ and for $n \geq 0$, let $x_{n+1} = 3x_n + \lfloor x_n \sqrt{5} \rfloor$. In particular, $x_1 = 5$, $x_2 = 26$, $x_3 = 136$, $x_4 = 712$. Find a closed-form expression for $x_{2007}$. ($\lfloor a \rfloor$ means the largest integer $\leq a$.)

Solution:
**First solution:** Observing that $x_2/2 = 13$, $x_3/4 = 34$, $x_4/8 = 89$, we guess that $x_n = 2^{n-1}F_{2n+3}$, where $F_k$ is the $k$-th Fibonacci number. Thus we claim that $x_n = \frac{2^{n-1}}{\sqrt{5}}(\alpha^{2n+3} + \alpha^{-(2n+3)})$, where $\alpha = \frac{1+\sqrt{5}}{2}$, to make the answer $x_{2007} = \frac{2^{2006}}{\sqrt{5}}(\alpha^{4017} + \alpha^{-4017})$.

We prove the claim by induction; the base case $x_0 = 1$ is true, and so it suffices to show that the recursion $x_{n+1} = 3x_n + \lfloor x_n \sqrt{5} \rfloor$ is satisfied for our formula for $x_n$. Indeed, since $\alpha^2 = \frac{3+\sqrt{5}}{2}$, we have
$$x_{n+1} - (3+\sqrt{5})x_n = \frac{2^{n-1}}{\sqrt{5}}\left(2(\alpha^{2n+5} + \alpha^{-(2n+5)}) - (3+\sqrt{5})(\alpha^{2n+3} + \alpha^{-(2n+3)})\right) = -2^n \alpha^{-(2n+3)}.$$
Now $2^n \alpha^{-(2n+3)} = (\frac{\sqrt{5}-1}{2})^3(3-\sqrt{5})^n$ is between 0 and 1; the recursion follows since $x_n, x_{n+1}$ are integers.

**Second solution:** (by Catalin Zara) Since $x_n$ is rational, we have $0 < x_n \sqrt{5} - \lfloor x_n \sqrt{5} \rfloor < 1$. We now have the inequalities
$$x_{n+1} - 3x_n < x_n \sqrt{5} < x_{n+1} - 3x_n + 1$$
$$(3+\sqrt{5})x_n - 1 < x_{n+1} < (3+\sqrt{5})x_n$$
$$4x_n - (3-\sqrt{5}) < (3-\sqrt{5})x_{n+1} < 4x_n$$
$$3x_{n+1} - 4x_n < x_{n+1} \sqrt{5} < 3x_{n+1} - 4x_n + (3-\sqrt{5}).$$
Since $0 < 3-\sqrt{5} < 1$, this yields $\lfloor x_{n+1} \sqrt{5} \rfloor = 3x_{n+1} - 4x_n$, so we can rewrite the recursion as $x_{n+1} = 6x_n - 4x_{n-1}$ for $n \geq 2$. It is routine to solve this recursion to obtain the same solution as above.

**Remark:** With an initial 1 prepended, this becomes sequence A018903 in Sloane's On-Line Encyclopedia of Integer Sequences: (http://www.research.att.com/~njas/sequences/).