1. ## inductive proof question

hello,

proving some predicate $\displaystyle A$ over the naturals $\displaystyle N$.

if the following statement holds for my base case, say $\displaystyle n = 1$

$\displaystyle A(n) \wedge A(n + 1)$

and i then assume it to hold for all $\displaystyle n \epsilon N$,
then i can also assume that $\displaystyle A(n)$ holds for all $\displaystyle n$.
i can hence take my inductive hypothesis as

$\displaystyle A(n) \rightarrow A(n + 1)$

but i already know that $\displaystyle A(n + 1)$ holds for all n.

this has got to be cheating right?

thanks for any pointers

2. Originally Posted by polypus
hello,

proving some predicate $\displaystyle A$ over the naturals $\displaystyle N$.

if the following statement holds for my base case, say $\displaystyle n = 1$

$\displaystyle A(n) \wedge A(n + 1)$

and i then assume it to hold for all $\displaystyle n \epsilon N$,
then i can also assume that $\displaystyle A(n)$ holds for all $\displaystyle n$.
i can hence take my inductive hypothesis as

$\displaystyle A(n) \rightarrow A(n + 1)$

but i already know that $\displaystyle A(n + 1)$ holds for all n.

this has got to be cheating right?

thanks for any pointers
Yes,
The error lies here:

Not only is it cheating you are assuming the result.

if the following statement holds for my base case, say $\displaystyle n = 1$

$\displaystyle A(n) \wedge A(n + 1)$

and i then assume it to hold for all $\displaystyle n \epsilon N$,

$\displaystyle A(1) \wedge A(2)$,

which tells you nothing about any $\displaystyle A(n),\ n>2$.

You have to assume that for some $\displaystyle k \in N$ that:

$\displaystyle A(k) \wedge A(k + 1)$

then prove that this implies:

$\displaystyle A(k+1) \wedge A(k+2)$.

But the approach working with $\displaystyle A(n)$ looks more natural to me

RonL