inductive proof question

**polypus** · September 15th 2007, 04:31 AM

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

**CaptainBlack** · September 15th 2007, 05:22 AM

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

Your base case is:

$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

Thread: inductive proof question

LinkBack

Thread Tools

Display

inductive proof question

Similar Math Help Forum Discussions

Proof by induction question - inductive step clarification?

inductive proof that the sum (r=0:n) of (n C r)^2 = (2n C n)

help me with Inductive Proof #2

quick question about inductive proof

Inductive proof

Search Tags