Prove that $f(x)^2+f(x+1)^2 = f(2x+1)$ for the function $f$ satisfying $f(x)=f(x-1)+f(x-2), f(1)=f(2)=1.$

Question

Prove that $f(x)^2+f(x+1)^2 = f(2x+1)$ for the function $f$ satisfying $f(x)=f(x-1)+f(x-2), f(1)=f(2)=1.$

I know how to prove it, but it is interesting so I am posting it.

The first hint is:

\begin{align} &\text{Try to prove this first: } \\ &f(x)=f(x-1)+f(x-2) \\ &=2f(x-2)+f(x-3) \\ &=3f(x-3)+2f(x-4) \\ &= 5f(x-4)+3f(x-3) \\ &= \cdot \cdot \cdot \end{align}

The second hint is:

$\text{According to the first hint: } f(x)=f(k+1)f(x-k)+f(k)f(x-k-1). $

Check this to see that your proof is the same as mine.

\begin{align} &f(x)=f(x-1)+f(x-2) = f(2)f(x-1)+f(1)f(x-2). \ \\ \ \\ &f(x-1)=f(x-2)+f(x-3) \\ &\Rightarrow f(x)=f(2)(f(x-2)+f(x-3))+f(1)f(x-2)=(f(1)+f(2))f(x-2) \\ &+f(2)f(x-3)=f(3)f(x-2)+f(2)f(x-3). \ \\ \ \\ &f(x-2)=f(x-3)+f(x-4). \\ &\Rightarrow f(x)=f(3)(f(x-3)+f(x-4))+f(2)f(x-3)=(f(2)+f(3))f(x-3) \\ &+f(3)f(x-4)=f(4)f(x-3)+f(3)f(x-4). \\ &\cdot \\ &\cdot \\ &\cdot \\ &\therefore f(x)=f(k+1)f(x-k)+f(k)f(x-k-1). \\ &x=2k+1; \ f(2k+1)=f(k)^2+f(k+1)^2. \\ \ \\ &\therefore f(x)^2+f(x+1)^2=f(2x+1).\end{align}

p.s. if you have another solution, please post it as an answer with a spoiler. (>! another answer with no enter)

Answer 1

My answer above:

\begin{align} &f(x)=f(x-1)+f(x-2) = f(2)f(x-1)+f(1)f(x-2). \ \\ \ \\ &f(x-1)=f(x-2)+f(x-3) \\ &\Rightarrow f(x)=f(2)(f(x-2)+f(x-3))+f(1)f(x-2)=(f(1)+f(2))f(x-2) \\ &+f(2)f(x-3)=f(3)f(x-2)+f(2)f(x-3). \ \\ \ \\ &f(x-2)=f(x-3)+f(x-4). \\ &\Rightarrow f(x)=f(3)(f(x-3)+f(x-4))+f(2)f(x-3)=(f(2)+f(3))f(x-3) \\ &+f(3)f(x-4)=f(4)f(x-3)+f(3)f(x-4). \\ &\cdot \\ &\cdot \\ &\cdot \\ &\therefore f(x)=f(k+1)f(x-k)+f(k)f(x-k-1). \\ &x=2k+1; \ f(2k+1)=f(k)^2+f(k+1)^2. \\ \ \\ &\therefore f(x)^2+f(x+1)^2=f(2x+1).\end{align}