I need help with a homework question. Thank you in advance!
Suppose that f is a function on the nonnegative integers such that f(0) = 0 and f(n) = n+f(n−1).
(A) Prove that f(n) = n(n+1)/2. Notice that this gives a third proof that 1 + 2 + · · · + n =
n(n+1)/2, because this sum satisfies the two conditions for f. (The sum has no terms and is thus 0
when n = 0.)
(B) Also find a formula if f(0)=3.
(A): I believe the induction portion for part A goes as follows:
We prove the formula for f by induction on n. If n = 0, then n(n+1)/2=0.
Assume that f(k-1) = ((k-1)k)/2
Then,
f(k) = k + f(k-1)
f(k) = k + ((k-1)k)/2
f(k) = k(k+1)/2
Therefore, the truth of the formula for n=k-1 implies its truth for n=k and thus by the principle of
induction, the formula for f holds true for all nonnegative integers n.
(B): I'm not too sure how to find the formula, but I know it has to be recursive. Once a closed formula is found, then it has to be proved with induction. Any tips for finding a formula for f(0)=3 would be appreciated for this part!
Your part (A) is basically correct. My only point is that when you state your assumption that $f(k-1) = \frac{(k-1)k}{2}$, you should also state it's for some $k \ge 1$.
As for part (B), note $f(1) = 1 + f(0) = 1 + 3$, $f(2) = 2 + f(1) = 2 + 1 + 3 = (2 + 1) + 3$, $f(3) = 3 + f(2) = 3 + (2 + 1) + 3 = (3 + 2 + 1) + 3$, etc. I assume you see a pattern here, which I'll leave to you to finish. However, dodoturkoz's question comment already states the result for you.