[Solved]: Solve the recurrence $f(n+1)=f(n)^2,\, f(0)=2$

Problem Detail: 

I have a problem with an exercise asking me to solve the following recurrence: $$f(n+1)=f(n)^2, \quad f(0)=2$$ Can someone explain how to solve this? I tried but couldn't.

Asked By : Roben

Answered By : Priyatham

$f(n) = 2^{2^n}$ will solve the recurrence.

• $f(0) = 2^1 = 2$
  
• $ f(n+1) = 2^{2^{n+1}} = 2^{2\cdot 2^n} = \left(2^{2^n}\right)^{2} = f(n)^2 $

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22657

3.2K people like this

 Download Related Notes/Documents