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


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


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

  • $\begingroup$ I got the second line, but how did you get the third line? $\endgroup$ – user2551612 Oct 12 '14 at 10:04
  • $\begingroup$ @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. $\endgroup$ – mathlove Oct 12 '14 at 10:06
  • $\begingroup$ I still can't figure how you got +1 for the third line can you explain? Thanks $\endgroup$ – user2551612 Oct 12 '14 at 10:11
  • $\begingroup$ Multiplied the 2 in. Think about this: $2*(2^a)=2^{a+1}$. Just let $a=2^{k-1}$, and you have his expression. $\endgroup$ – FundThmCalculus Oct 12 '14 at 10:13
  • $\begingroup$ @user2551612: I added a bit. Take a look. I hope that helps. $\endgroup$ – 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...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.