I've been working on this problem:
Determine whether each of these proposed definitions is a valid recursive definition of a function f from the set of nonnegative integers to the set of integers. If f is well defined, find a formula for f (n) when n is a nonnegative integer and prove that your formula is valid.
c) $f(0) = 2$, $f(1) = 3$, $f(n) = f(n − 1) − 1$ for $n ≥ 2$
What I had originally wrote as a proof (by induction):
Let P(n) be the statement $n+2$, where n is an integer greater than 0.
Basis Step: P(0) is true: $P(0) = 0 + 2 = 2$
P(1) is true: $P(1) = 1 + 2 = 3$
Inductive Step: Suppose P(k) is true for all k≥2. Then P(k+1) is true as well. Our goal is to prove that $P(k+1)=(k+1)+2=k+3$.
$P(k+1)=P(k+1-1)-1$
$=P(k)-1$
$=k+2-1$
$=k+1$
This is impossible, so I knew I was wrong, but I don't understand how this formula couldn't work (especially after looking at the book's answer for the right formula).
I'll paste the book's answer for it:
c) $f(n) = 4 − n$ if $n > 0$, and $f(0) = 2$.
Basis step: $f(0) = 2$ and $f(1) = 3 = 4 − 1$.
Inductive step (with $k ≥ 1$): $f(k + 1) = f(k) − 1 = (4 − k) − 1 = 4 − (k + 1)$.
My two major questions are:
Question 1) How does the book's formula ($4-n$) actually work? I thought ($n+2$) would work since it satisfies both f(0) and f(1).
Question 2) How is the book able to just say that $f(0)=2$ without proving it in the basis step?
The book can say $f(0)=2$ because you're given that $f(0)=2.$ If you actually plug in the first few values of $n$ into the recursion formula that you're given (remembering that you're told the recursion formula is only valid for $n \geq 2$), you'll see that the book's answer is correct.
The purpose of this exercise is to demonstrate that you have to be careful about where you start the induction. If something "different" is going on for low numbers (as is the case here), you have to handle those numbers separately and start the induction when the general case takes over.