Sunday, January 1, 2023

A putnam sequence problem

 Let $a_n$ be a sequence such that


$$a_1 = a \ge 2$$

and

$$a_{n+1} = a_{n}^2 - 2$$


Show that 


$$\left(1 - \frac{1}{a_1}\right)\left(1 - \frac{1}{a_2}\right)\dots = \prod_{n \ge 1} \left(1 - \frac{1}{a_n}\right) = \frac{\sqrt{a^2 - 4}}{1 + a}$$


The putnam problem was with $a = \frac{5}{2}$



Scroll down for a solution.




Since $a \ge 2$, we can find a $u \ge 1$ such that $a = u + \frac{1}{u}$ (for $a = \frac{5}{2}, u =2$).

The case $a = 2, u = 1$ is easy, so assume $u \gt 1$.


The recurrence then gives us


$$a_{n+1} = u^{2^n} + \frac{1}{u^{2^n}}$$


Let $$f(x) = \left(1 - \frac{1}{x + \frac{1}{x}}\right) = \frac{x^2 - x + 1}{x^2 + 1}$$


The value we are seeking is


$$f(u)f(u^2)f(u^4)f(u^8)\dots f(u^{2^n})\dots$$


Now notice that

$$(x^2 - x + 1)(x^2 + x + 1) = (x^2 + 1)^2 - x^2 = x^4 + x^2 + 1$$


Thus if we multiply


$$(x^2 - x +1)(x^4 - x^2 + 1)(x^8 - x^4 + 1)\dots(x^{2^{n}} - x^{2^{n-1}} + 1) $$

with $x^2 + x + 1$ we get

$$(x^2 + x + 1)(x^2 - x +1)(x^4 - x^2 + 1)(x^8 - x^4 + 1)\dots(x^{2^{n}} - x^{2^{n-1}} + 1)  = $$

$$(x^4 + x^2 + 1)(x^4 - x^2 + 1)\dots(x^{2^{n}} - x^{2^{n-1}} + 1)  = x^{2^{n+1}} + x^{2^n} + 1$$

and similarly using 

$$(x^2 - 1)(x^2 + 1) = x^4 - 1$$

we get

$$(x^2 - 1)(x^2 + 1)(x^4 + 1) \dots (x^{2^n} + 1) = x^{2^{n+1}} - 1$$

Since


$$\frac{x^{2^{n+1}} + x^{2^n} + 1}{x^{2^{n+1}} - 1} \to 1$$


(for $x >1$)


We see that


$$L = f(u)f(u^2)\dots f(u^{2^n})\dots = \frac{u^2 - 1}{u^2 + u + 1}$$

This we can rewrite as

$$ L = \frac{u - \frac{1}{u}}{u + \frac{1}{u} + 1} $$

Squaring gives


$$L^2 = \frac{u^2 + \frac{1}{u^2} - 2}{(a+1)^2} = \frac{a^2 -4}{(a+1)^2}$$

Thus 


$$ L = \frac{\sqrt{a^2 - 4}}{a+1}$$


No comments:

Post a Comment