Let $f_0=1$, $f_1=1$, $f_2=1$, $f_{n}=\frac{f_{n-1}f_{n-2}+1}{f_{n-3}}$ for $n\geq{3}$
Prove that $f_n$ is always an integer.
I tried to use induction, but the calculations were messy and unenlightening.
I experimented and saw that for the more general $f_0=1$, $f_1=1$, $f_2=1$, $f_{n}=\frac{f_{n-1}f_{n-2}+k}{f_{n-3}}$, $f_n$ appears to always be an integer.
I tried to see if there was a pattern for this general case, but couldn't find one.
Any tips here?
Best Answer
When induction doesn't seem to work, your inductive hypothesis is probably too weak. We'll take $k$ as a positive integer. If you work out the first few terms of this sequence, you should notice that eventually the difference between consecutive terms changes every other term, and you should spot a recurrence relation between three consecutive values for this difference. This implies a recursion relation between $f_n,\,f_{n-2},\,f_{n-4}$ that would prove the sequence only contains integers. So, let's get to the proof.
Note that $f_3=k+1,\,f_4=2k+1$ are also integers, so that's five in a row. Define $$u_n:=f_n-(2k+2)f_{n-2}+f_{n-4}\\=\frac{f_{n-1}f_{n-2}+k-(2k+2)f_{n-2}f_{n-3}+f_{n-4}f_{n-3}}{f_{n-3}}\\=\frac{f_{n-2}u_{n-1}}{f_{n-3}},$$where we've used $k+f_{n-4}f_{n-3}-f_{n-2}f_{n-5}=0$, a rearrangement of the original recursion relation (with an $n\mapsto n-2$ shift). (Note that $f_{n-3}\ne 0$ because we can easily prove by induction that all $f_n$ are positive.) Thus we can prove by induction that $u_n=0$ for $n\ge 4$, with base case $u_4=2k+1-1(2k+2)+1=0$.