Define a recurrence term. With a given definion

Question

My question is the following.

Define $f_n = 2^{2^{n}}+1$ show that for all $n \geq 1$, $f_n = f_0f_1 ...f_{n-1} + 2$

I have the following

Base case unsure how to prove it

Induction step suppose $f_0f_1 ...f_{n-1} = f_n -2$ then will show $n+1$ is also true

$f_0f_1 ...f_{n-1}f_n = f_{n+1} -2$

$(f_n -2)f_n=f_{n+1} -2 $

$(2^{2^{n}} -1)(2^{2^{n}} + 1)=f_{n+1} -2 $

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

Not sure where to go from there, any ideas?

Answer 1

You're almost done $2^{2^{n+1}}-1=f_{n+1}-2$ just add $+2$ to both sides and you'll get $f_{n+1}=2^{2^{n+1}}+1$ which is true by definition.

Another way could be to apply difference of squares multiple times $f_{n}-2=2^{2^n}-1=\color{red}{(2^{2^{n-1}}-1)}(2^{2^{n-1}}+1)=\color{red}{(2^{2^{n-2}}-1)}(2^{2^{n-1}}+1)(2^{2^{n-2}}+1)=\cdots=(2^{2^{n-1}}+1)(2^{2^{n-2}}+1)\cdots(2^{2^{1}}+1)(2^{2^{0}}+1)=f_{n-1}f_{n-2}\cdots f_1f_0$