Recursion Question - Trying to understand the concept 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?
 A: 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...
A: 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$$
A: 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.
