# 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$

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

## 3 Answers

\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}.$$

• I got the second line, but how did you get the third line? – user2551612 Oct 12 '14 at 10:04
• @user2551612: I used $a(b+c)=ab+ac$ for the first term, and $(d+e)^2=d^2+2de+e^2$ for the second term. – mathlove Oct 12 '14 at 10:06
• I still can't figure how you got +1 for the third line can you explain? Thanks – user2551612 Oct 12 '14 at 10:11
• Multiplied the 2 in. Think about this: $2*(2^a)=2^{a+1}$. Just let $a=2^{k-1}$, and you have his expression. – FundThmCalculus Oct 12 '14 at 10:13
• @user2551612: I added a bit. Take a look. I hope that helps. – mathlove Oct 12 '14 at 10:14

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

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...