1
$\begingroup$

To prove a statement about recursive series, is it correct to use an inductive proof structure showing that if $n = k$ and $n = k + 1$ are true then $n = k + 2$ holds true, and then prove the statement for $n = 1$, $2$ base cases?

$\endgroup$
1
  • 1
    $\begingroup$ If the induction base is checked for the cases $n = 1$ and $n = 2$, it is sufficient to make the inductive step $n=k \rightarrow n=k+2$ $\endgroup$
    – Roman83
    Commented Apr 11, 2016 at 6:06

1 Answer 1

0
$\begingroup$

Yes.

It is equivalent to making a new statement, $P(n) \equiv (S(n) \land S(n+1))$.

When you check $S(1)$ and $S(2)$, you determine $P(1)$. Then you inductively prove $P(n) \implies P(n+1)$ as $(S(n)\land S(n+1)) \implies S(n+2)$. And given $S(n+1)$ you get $S(n+1)\land S(n+2)$ which is $P(n+1)$.

Finally, once $P$ is proven for all $n$, it implies $S$ for all $n$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .