0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ You could. Nothing wrong with that. Just make sure the next even/odd is $n +2$ and not $n+1$. But you can also to a "split-level induction where if $a_n = \frac n2 + 1$ then $a_{n+1} = \frac {(n+1)-1}2 + 1$ and $a_{n+2} = \frac {n+2} 2 + 1$. $\endgroup$ – fleablood Apr 18 '18 at 17:51
  • $\begingroup$ Proving with 2 inductions establishes $$\bigg(\forall x.A(x)\bigg) \land \bigg(\forall x.B(x)\bigg)$$ Proving with 1 induction establishes $$\forall x.\bigg(A(x) \land B(x)\bigg)$$ Those are equivalent statements. $\endgroup$ – DanielV Apr 18 '18 at 18:49
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.