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