Proof by induction when there are two cases?

Question

I'm trying to show that the LHS of an equation equals the first equation below if $n$ is even and it equals the second equation below if $n$ is odd.

[ { \begin{array}{ll} \frac{n}{2} + 1 \hspace{0.3cm} \text{if $n$ is even}\\ \\ \frac{n-1}{2} +1 \hspace{0.3cm} \text{if $n$ is odd} \end{array}

I want to prove this by induction so do I have to do the inductive proof twice, i.e. for when $n$ is even and for when $n$ is odd?

Answer 1

That depends on what other cases you need to refer back to when doing the inductive step.

If for proving the even cases you need to refer to any of the odd cases 'before' it (or vice versa), then no, you should still do one induction, but just handle the even and odd cases separately.

On the other hand, if the even cases can all be proved by reference to 'earlier' even cases only,, and same for the odd numbers, then you could indeed do two separate inductive proofs ... but even in that case you could still set it up as one inductive proof and again just handle the even and odd cases separately.

Answer 2

You could

• show that $f(n)=f(n-2)+1$ for all $n\ge 2$
• with two bases cases $f(0)=1$, $f(1)=1$

or you could

• show that, for all $n\ge 1$, $$f(n)=\begin{cases}f(n-1)&\text{if }n\text{ is odd}\\f(n-1)+1&\text{if }n\text{ is odd}\end{cases}$$
• with just one base case $f(0)=1$.

or you could

• use induction to show that $f(2n)=n+1$ for all $n$
• use induction to show that $f(2n+1)=n+1$ for all $n$