Recursion Question - Trying to understand the concept

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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.