1) Assuming that f(0) = 0, show that f(n) = n * (n+1) / 2 satisfies the equation:
f(n) = n + f(0) + f(n-1)
2) Show that g(n) = n log n, satisfies the equation:
g(n) = n + 2g * (n/2)
Well we are given f(n) and f(0) so lets start by plugging them in first.
$\displaystyle \displaystyle \frac{n(n+1)}{2}=n+0+\frac{(n-1)n}{2}=n+\frac{n(n-1)}{2}=\frac{2n+n(n-1)}{2}=.....$
You should be able to finish this and use the same methodology for number 2.
As a side note, $\displaystyle \displaystyle \frac{n(n+1)}{2}=\sum_{i=1}^{n}i$
I just plugged in the values to the equation. We were given f(n) and f(0) so I substitute those in to the equation f(n)=n+f(0)+f(n-1).
For f(n-1), I plugged in n-1 for n in the f(n) equation. Thus, $\displaystyle \displaystyle f(n-1)=\frac{(n-1)(n-1+1)}{2}$ and simplify. Now, we have all pieces to our f(n) equation. From here, your goal is to make the left hand side(LHS) look like the RHS.