0
 I am looking at the solution of the following question and wondering how is f(7) equal to 247  in line 1 ?

Given a recursive formula in (1), find the value of f(7) 
f(n) =  (2f(n − 1) + n if n > 0
         and 0 if n = 0

1.f(7) = 2f(6) + 7 = 247
2.f(6) = 2f(5) + 6 = 120
3.f(5) = 2f(4) + 5 = 57
4.f(4) = 2f(3) + 4 = 26
5.f(3) = 2f(2) + 3 = 11
6.f(2) = 2f(1) + 2 = 4
7.f(1) = 2f(0) + 1 = 1
8.f(0) = 0
user4203815
  • 95
  • 1
    They have applied the recursive definition from step 1 to step 8 until they got down to an actual number and then fed these numbers back up from step 8 to step 1. e.g. in step 7 they used the result of step 8 to replace f(0) with 0. – Mufasa Mar 30 '15 at 20:48
  • But how do these add up to 247 in line 1 ? – user4203815 Mar 30 '15 at 21:37
  • Look at the explaination given by @MichaelSmith below - he has explained what I was trying to say above. – Mufasa Mar 30 '15 at 21:38

1 Answers1

2

I'm going to spell out what I think Mufasa means in their comment. First you write:

$$f(7) = 2\;f(6)+7$$

But you don't know what $f(6)$ is. So you try to compute that:

$$f(6) = 2\;f(5) + 6$$

But you don't know what $f(5)$ is either. So you want to compute that, which requires you to work out $f(4)$, which requires $f(3)$, which requires $f(2)$, which requires $f(1)$. But that last one we can do:

$$f(1) = 2\;f(0) + 1 = 2(0) + 1 = 1$$

Now we can backchain:

$$\begin{eqnarray*} f(1) &=& 1\\ f(2) &=& 2\;f(1)+2 = 2(1)+2 = 4\\ &\vdots&\\ f(7) &=& 2\;f(6)+7 = 2(120)+7 = 247 \end{eqnarray*}$$

Community
  • 1
Michael Smith
  • 130