# help me with Inductive Proof #2

• Oct 16th 2009, 05:05 PM
zpwnchen
help me with Inductive Proof #2
\$\displaystyle n^2-1\$ is divisible by 8 whenever n is an odd positive integer

1) Basic step: P(1) = 1-1 =0 is divisible by 8.

2) inductive step:
hypothesis:\$\displaystyle P(k): k^2-1\$ is divisible by 8

conclusion: \$\displaystyle P(k+2): (k+2)^2 -1\$ is divisible by 8?
OR
\$\displaystyle P(k+1): (k+1)^2 -1\$ is divisible by 8? <- to make it odd

help me pls
• Oct 17th 2009, 03:20 AM
tonio
Quote:

Originally Posted by zpwnchen
\$\displaystyle n^2-1\$ is divisible by 8 whenever n is an odd positive integer

1) Basic step: P(1) = 1-1 =0 is divisible by 8.

2) inductive step:
hypothesis:\$\displaystyle P(k): k^2-1\$ is divisible by 8

conclusion: \$\displaystyle P(k+2): (k+2)^2 -1\$ is divisible by 8?
OR
\$\displaystyle P(k+1): (k+1)^2 -1\$ is divisible by 8? <- to make it odd

help me pls

It is P(k+2), of course: if k is an odd positive integer, the next ODD integer is k + 2, not k + 1.

Without induction: n^2 - 1 = (n-)(n+1). As n is odd, exactly one of n-1 or n+1 is divisible by 4 and the other factor is even ==> the whole thing is divisible by 4*2 = 8.

Tonio