1. ## inductive proof question

hello,

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

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

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

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

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

but i already know that $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 $A$ over the naturals $N$.

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

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

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

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

but i already know that $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 $n = 1$

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

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

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

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

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

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

then prove that this implies:

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

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

RonL