Recursion problem help

Question

The following are the teachers example problems. The issue is that I don't understand the exact steps they took to go from $f(0)$ to $f(1)$ to $f(2)$ to $f(3)$. What I'm asking here is if someone could be so kind to show me how the answers for $f(0)\ldots f(3)$ are derived for each problem.

Let $f$ be defined as follows: $f(0) = 3$

$f(n) = (−1)^nf(n−1) + 4n$ for $n\ge1$.

Find $f(7)$

The correct answer is $3$

$f(0) = 3$

$f(1) = 1$

$f(2) = 9$

$f(3) = 3$

$f(4) = 19$

$f(5) = 1$

$f(6) = 25$

$f(7) = 3$

Let $f$ be defined as follows:

$f(0) = 1$

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

Find $f(6)$

The correct answer is $22$

$f(0) = 1$

$f(1) = 2$

$f(2) = 4$

$f(3) = 7$

$f(4) = 11$

$f(5) = 16$

$f(6) = 22$

Let $f$ be defined as follows:

$f(0) = 4$

$f(1) = 3$

$f(n) = f(n−1) + 3f(n−2)$ for $n≥2$.

Find $f(6)$

The correct answer is $348$

$f(0) = 4$

$f(1) = 3$

$f(2) = 15$

$f(3) = 24$

$f(4) = 69$

$f(5) = 141$

$f(6) = 348$

Answer 1

The first recurrence is $f(n)=(-1)^nf(n-1)+4n$ for $n\ge 1$, with initial value $f(0)=3$. Just plug in successive values of $n$, starting with $n=1$:

$$\begin{align*} f(1)&=(-1)^1f(0)+4\cdot1=(-1)(3)+4=-3+4=1\\ f(2)&=(-1)^2f(1)+4\cdot2=1\cdot1+8=9\\ f(3)&=(-1)^3f(2)+4\cdot3=(-1)(9)+12=3\\ f(4)&=(-1)^4f(3)+4\cdot4=1\cdot3+16=19\;, \end{align*}$$

and so on.

The second recurrence is $f(n+1)=f(n)+n$ for $n\ge 0$, with initial value $f(0)=1$. To find $f(1)=f(0+1)$, you need to take $n=0$:

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

Continue in similar fashion, taking $n$ to be in succession $1,2,3$, and so on:

$$\begin{align*} f(2)&=f(1+1)=f(1)+1=1+1=2\\ f(3)&=f(2+1)=f(2)+2=2+2=4\\ f(4)&=f(3+1)=f(3)+3=4+3=7\;, \end{align*}$$

and so on.

The third recurrence is $f(n)=f(n-1)+3f(n-2)$ for $n\ge 2$, with initial values $f(0)=4$ and $f(1)=3$. Like the first one, this one gives you $f(n)$ instead of $f(n)$, so you can proceed very straightforwardly, just as with the first one:

$$\begin{align*} f(2)&=f(1)+3f(0)=3+3\cdot4=15\\ f(3)&=f(2)+3f(1)=15+3\cdot3=24\\ f(4)&=f(3)+3f(2)=24+3\cdot15=24+45=69\;, \end{align*}$$

and so on.

In every case it’s just a matter of substituting the appropriate value of $n$ into the recurrence, and if you’ve already computed the values of $f$ that appear on the righthand side of the recurrence, you can use them to compute the desired value.

Answer 2

You are given $f(0)=3$ and $$\tag1f(n)=(-1)^nf(n)+4n\quad\text {for }n\ge 1.$$ To compute $f(1)$, you let $n=1$ in equation $(1)$, i.e. $f(1)=(-1)^1f(1-1)+4\cdot 1$. Since you knwo $f(09=3$, this gives you $f(1)=(-1)^1\cdot 3+4=1$. To compute $f(2)$, you let $n=2$ in $(1)$, which gives you $f(2)=(-1)^2f(1)+4\cdot 2 = 1\cdot 1+8=9$. You should be able to veify the rest now.

Especially, do you see why we need two "starting values" in the last example? The first you get, letting $n=2$ in $f(n)=f(n-1)+3f(n-2)$, is $f(2)=f(1)+3f(0)=3+3\cdot 4=15$ so it's good that both $f(0)$ and $f(1)$ wer explicitly given, after that $f(3)=f(2)+3f(1)=15+3\cdot 3=24$.