Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Just trying to grasp this concept and was hoping someone could help me a bit. I am taking a discrete math class. Can someone please explain this equation to me a bit?

$f(0) = 3$

$f(n+1) = 2f(n) + 3$

$f(1) = 2f(0) + 3 = 2 \cdot 3 + 3 = 9$

$f(2) = 2f(1) + 3 = 2 \cdot 9 + 3 = 21$

$f(3) = 2f(2) + 3 = 2 \cdot 21 + 3 = 45$

$f(4) = 2f(3) + 3 = 2 \cdot 45 + 3 = 93$

I do not see how they get the numbers to the right of the equals sign. Please someone show me how $f(2) = 2f(1) + 3 = 2 \cdot 9 + 3$. I see they get "$2\cdot$" because of $2f$ but how and where does the $9$ come from? I also see why the $+3$ at the end of each equation but how and where does that number in the middle come from?

share|improve this question
    
wich number "in the middle" do you mean? –  Amire Jul 12 '13 at 1:51
add comment

3 Answers

up vote 4 down vote accepted

Simply use substitution.

We are given the initial value $$\color{blue}{\bf f(0) = 3}\tag{given}$$

Each subsequent value of the function $f$ depends on the preceding value. So the function evaluated at $(n + 1)$ depends (is defined, in part) on the function's value at $n$: That's what's meant by a recursive definition of the function $f$, which here is defined as: $$f(n+1) = 2\cdot f(n) + 3,\quad \color{blue}{f(0) = 3}$$

Knowing $f(0)$ is enough to "get the ball rolling":

$${\bf f(0 + 1) = f(1)} = 2\color{blue}{\bf f(0)} + 3 = 2\cdot \color{blue}{\bf 3} + 3 = 6 + 3 = \bf 9$$

Now, knowing $f(1)$ we can compute $f(2)$

$$f(1 + 1) =f(2) = 2\cdot {\bf f(1)} + 3 = 2\cdot {\bf 9} + 3 = 18 + 3 = {21}$$

Now that we know $f(2) = 21$ we can find $f(2 + 1) = f(3)$:

$$f(3) = 2\cdot f(2) + 3 = 2 \cdot 21 + 3 = 42 + 3 = 45$$

Now that we know $f(3) = 45$, we can compute $f(3+1)=f(4)$:

$$f(4) = 2\cdot f(3) + 3 = 2\cdot 45 + 3$$

And so on...

share|improve this answer
    
Thank You this made it much clearer. –  John Smith Jul 12 '13 at 2:29
    
You're welcome! –  amWhy Jul 12 '13 at 2:30
    
@amWhy: excellent feedback! :-) +1 –  Amzoti Jul 13 '13 at 0:27
add comment

The function $f$ is given by a starting condition $f(0)=3$, and by the condition $f(n+1)=2\cdot f(n)+3$. This means that we calculate the value of $f(2)$ from the value of $f(1)$, which itself is calculated from $f(0)$ -- which was given to us.

$$f(1)=9\implies f(2)=2\cdot f(1)+3=2\cdot 9+3$$

share|improve this answer
    
Thank you very much this made it much clearer. I didn't realize f(1) was referencing the answer to the equation. –  John Smith Jul 12 '13 at 2:28
add comment

Perhaps by considering a different sequence this may become clearer:

$$f(0)=0$$ $$f(n+1)=n+1$$

therefore

$$\begin{align} f(n=1)&=f(n=0)+1=0+1=1\\ f(n=2)&=f(n=1)+1=(f(n=0)+1)+1=(0+1)+1=2\\ f(n=3)&=f(n=2)+1=(f(n=1)+1)+1=((f(n=0)+1)+1)+1=((0+1)+1)+1=3\\ \end{align}$$

So this will generate all the natural numbers.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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