1

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?

Björn Friedrich
  • 3,747
Afiq Hatta
  • 239
  • 1
    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$ – Roman83 Apr 11 '16 at 06:06

1 Answers1

0

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$.

CiaPan
  • 13,049