Proof by induction that $f(n) = 1-2^{2^n}$, where $f(0) = 3$ and $f(n) = 2 f(n-1) - (f(n-1))^2$

Question

I am doing a textbook question which state that a function $f:\mathbb{N}\to\mathbb{Z}$ is a recursively defined as shown bellow

$f(0) =3$,

$f(n) = 2\cdot f(n-1) -(f(n-1))^2 $ if $n\ge1$.

Prove that $f(n) = 1-2^{2^n}$ for all integer $n\ge1$.

I am trying to prove this by induction, so I started by using my base step :

Let $n=1 : f(1) = -3 $

then I did the inductive step for $n = k-1$ which gave me $f(k-1) = 1-2^{2^{k-1}}$ but I don't know how to proceed from here.. can one explain. thanks

Answer 1

$$\begin{align}f(k)&=2f(k-1)-(f(k-1))^2\\&=2 \left(1-2^{2^{k-1}}\right)-\left({1-2^{2^{k-1}}}\right)^2\\&=2-2^{2^{k-1}+1}-\left(1-2^{2^{k-1}+1}+2^{2^k}\right)\\&=1-2^{2^{k}}.\end{align}$$

P.S.

$$2\left(1-2^{2^{k-1}}\right)=2-2^1\cdot 2^{2^{k-1}}=2-2^{1+2^{k-1}}=2-2^{2^{k-1}+1}.$$

$$\left(1-2^{2^{{k-1}}}\right)^2=1^2-2\cdot 1\cdot 2^{2^{k-1}}+\left(2^{2^{k-1}}\right)^2=1-2^{2^{k-1}+1}+2^{2^{k-1}\times 2}.$$

Answer 2

Hint: $$ \left(1-2^{2^{n-1}}\right)\!\!\left(1+2^{2^{n-1}}\right)=\left(1-2^{2^{n}}\right)$$

Answer 3

Then $f(k)=2f(k-1)-f^2(k-1)=2(1-2^{2^{k-1}})-(1-2^{2^{k-1}})^2$. do the math...