0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Your edit radically changed the question, and invalidated all of the existing answers. Please don't do that. $\endgroup$
    – D.W.
    Mar 17 '14 at 0:25
  • 1
    $\begingroup$ Try "running" the recurrence a few steps, guess an answer, prove by induction. $\endgroup$
    – vonbrand
    Mar 17 '14 at 0:40
  • 1
    $\begingroup$ This is a dump of an exercise problem, not a question. If you have a specific question regarding the wording of the problem or concrete steps in your own attempts at solving the problem, feel free to edit accordingly and we can reopen the question. See also here for our homework policy, and here for a relevant discussion. You may also want to check out our reference questions. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$
    – Raphael
    Mar 17 '14 at 15:59
  • $\begingroup$ You know that f(0)=2 and by substituting that f(0 + 1) = f(0)^2 = 2^2 = 4. You substitute again and see that f(1 + 1) = f(1)^2 = 4^2 = 16. Etc... $\endgroup$ Mar 17 '14 at 19:29
3
$\begingroup$

$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 $
$\endgroup$
5
  • $\begingroup$ but you are just guessing that f(n)=2^2^n do i need to find it or just to guess $\endgroup$
    – Roben
    Mar 15 '14 at 19:43
  • $\begingroup$ In general, you always solve a recurrence relation by showing that a particular $f$ satisfies both the initial condition and the relation. How we arrived at $f$ is not of any concern. $\endgroup$
    – Priyatham
    Mar 15 '14 at 19:49
  • 1
    $\begingroup$ @Roben There are a few methods to solve recurrence relations, among them "guessing" + induction. The "guessing" part of that method basically consists of trying the first couple of values to see whether you can spot a pattern. If you want to read about this stuff, a professor at my university who teaches one of the courses on efficient algorithms included a chapter on solving recurrences, which can be found here. It is a little theory-heavy, though. $\endgroup$
    – G. Bach
    Mar 16 '14 at 1:10
  • $\begingroup$ @Roben Just wanted to add that this is generalizable to any exponent $k\in N$. $$f(n+1)=f(n)^k, f(0)=k$$. $\endgroup$
    – mrk
    Mar 16 '14 at 9:13
  • $\begingroup$ Please consider not to encourage undesirable posting behaviour. $\endgroup$
    – Raphael
    Mar 17 '14 at 16:00
4
$\begingroup$

Hint, Consider the function $g(n) = \log_2 f(n)$

$\endgroup$
3
$\begingroup$

We are given $f(n+1) = f(n)^2$. Now, recursively write $f(n)$ also in the given form. So, if we write it recursively we get the following equations$$f(n+1)=f(n)^2$$ $$f(n)=f(n-1)^2$$ So, using above two equations, $$f(n+1)=f(n-1)^4$$ This doesn't seem to give any hint (If you see any pattern here, great). So, expand more. $$f(n-1) = f(n-2)^2$$ Putting it again in the equation gives, $$f(n+1) = (f(n-2)^2)^4 = f(n-2)^8$$ Now, the patterns becomes clear. For each value you subtract from $n$, power of the function value multiplies by 2. So, we can generalize saying $$f(n+1)=f(n+1-x)^{2^x}$$ We have not yet made use of the base case given. We know $f(0) = 2$. So, put $x=n+1$. We get $$f(n+1) = 2^{2^{(n+1)}}$$ Finally, we get our answer $f(n) = 2^{2^n}$.

This is basically what Priyatham has said, but there is also a way of making guesses. It's not left entirely to your luck

$\endgroup$
5
  • $\begingroup$ Can you solve also this one Prove the recurrence solution : f(n)= { 2 n=1 ---------------------------------------------------------------- { f(n-1)+3=3n-1 otherwise $\endgroup$
    – Roben
    Mar 16 '14 at 13:40
  • $\begingroup$ Try to solve it!! $\endgroup$
    – nitishch
    Mar 16 '14 at 14:12
  • 3
    $\begingroup$ @Roben We won't do your homework for you. $\endgroup$ Mar 17 '14 at 2:32
  • $\begingroup$ Please consider not to encourage undesirable posting behaviour. $\endgroup$
    – Raphael
    Mar 17 '14 at 16:00
  • $\begingroup$ Oh.. Will try to follow it next time. Thanks $\endgroup$
    – nitishch
    Mar 17 '14 at 16:59

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