If $x_0=x_1=1$, and for $n\geq1$ $x_{n+1}=\frac{x_n^2}{x_{n-1}+2x_n}$, find a formula for $x_n$ as a function of $n$.
Problem
Source: Puerto Rico 2013 TST #4
Tags: algebra, recursion, function
01.05.2015 09:48
$x_n=\frac{1}{(2n-1)!!}$ Easy to prove by induction: let $x_n=\frac{1}{(2n-1)!!}$, and $x_{n-1}=\frac{1}{(2n-3)!!}$ then $x_{n+1}=\frac{1}{((2n-1)!!)^2\cdot (\frac{2}{(2n-1)!!}+\frac{2n+1}{(2n-1)!!})}=\frac{1}{(2n-3)!!}$
01.05.2015 10:13
Clearly $x_n > 0$ for all $n\geq 0$. Denoting $y_n = \dfrac {x_{n-1}}{x_n}$ for $n\geq 1$ we get $y_1=1$ and $y_{n+1} = y_n + 2$ for $n\geq 1$, so $y_{n} = 2n-1$ for $n\geq 1$. But then the product of $y_1,y_2,\ldots, y_n$, equal to $(2n-1)!!$, telescopes to $\dfrac {1}{x_n}$. Thus we don't have to "guess" the form of $x_n$.
31.05.2015 12:22
NikitaSkybytskyi wrote: $x_n=\frac{1}{(2n-1)!!}$ Easy to prove by induction: let $x_n=\frac{1}{(2n-1)!!}$, and $x_{n-1}=\frac{1}{(2n-3)!!}$ then $x_{n+1}=\frac{1}{((2n-1)!!)^2\cdot (\frac{2}{(2n-1)!!}+\frac{2n+1}{(2n-1)!!})}=\frac{1}{(2n+1)!!}$ There is a typo