1
$\begingroup$

Note: This problem is from Discrete Mathematics and Its Applications [7th ed, prob 35, pg 330].

Problem:
a) Use mathematical induction to prove that $n^2$ - 1 is divisible by 8 whenever n is an odd positive integer.

My work:
I defined predicate P(n) as $n^2$- 1 is divisible by 8
My basis step was showing P(1), as 1 is the first odd positive integer
P(1) - 8 | $1^2$ - 1 or 8 | 0 which is true
My inductive hypothesis is to assume P(k) for some odd positive integer k and use that to show P(k+2)
So inductive hypothesis - P(k) - $k^2$ - 1 = 8c where s is some integer
Now the next odd positive integer is at k+2 so we have
8| (k + 2)$^2$ - 1
8 | k$^2$ - 1 + 4k + 4
I was able to recognize the k$^2$ - 1 segment from my inductive step so I made an immediate substitution for that, now we have
8 | 8c + 4k + 4.
I recognized that the 8c portion was divisible by 8 but what mathematical steps can you go to show that 4k + 4 is also divisible by 8?

$\endgroup$
  • $\begingroup$ $4k+4=4(k+1)$ and $k+1$ is even by assumption. $\endgroup$ – symplectomorphic Mar 6 '15 at 17:55
  • 1
    $\begingroup$ See the answer below for a good hint. But I'll critique your proof right at the "...so we have 8 | ..." We don't "have" that, it's what we need to prove. Writing it down and then "deducing" that 8|8 or some other obviously true statement is not a valid proof method. $\endgroup$ – John Brevik Mar 6 '15 at 17:57
  • $\begingroup$ @symplectomorphic but k could be 3, meaning 4(3) or 12 and 12 isn't divisible by 8. $\endgroup$ – committedandroider Mar 6 '15 at 18:05
  • $\begingroup$ @committedandroider You're basically done: remember that $k$ is odd so $k=2m+1$ for some integer $m$ and thus $4k+4=8m+8$ which is divisible by $8$. The proof can be shortened somewhat. Please see my answer below as an example. $\endgroup$ – Kim Jong Un Mar 6 '15 at 18:06
  • 1
    $\begingroup$ @KimJongUn Thanks great supreme leader :) $\endgroup$ – committedandroider Mar 6 '15 at 18:09
1
$\begingroup$

If it is insisted that induction is used, it's enough after checking the base case to note that $$ (2k+3)^2-1=4k^2+12k+8=(8k+8)+4k^2+4k=\color{blue}{8(k+1)}+\color{red}{[(2k+1)^2-1]}. $$ The $\color{blue}{\text{blue}}$ part is clearly divisible by $8$ whereas the induction hypothesis says $8$ divides the $\color{red}{\text{red}}$ part.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Hint: Remember that you defined $k$ to be an odd integer $k$. If $k$ is odd then you can write it as... So $4k + 4$ can be written as...

Very good work otherwise. Just keep track of what pieces of information you defined earlier on.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Since $k$ is odd, let $k = 2p + 1$ where $p$ is an integer, so you will be able to complete the proof.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Another proof (without induction)

Set $n=2k+1$ for some $k\in \mathbb N$. Then we want to see that $(2k+1)^2-1$ is divisible by 8

We have $(2k+1)^2-1=4k^2+4k=4k(k+1)$ depending on the value of $k$ we have that $k$ is even or $(k+1)$ is even. So a factor of the RHS is a product of $4$ and an even number, which is clearly divisible by $8$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Let $n = 2k+1$ and $n^2-1$ is divisible by 8 $\tag1$.

All you have to prove is for $n+2 = 2k+3$, $(n+2)^2-1$ is divisible by 8$\tag2$

From 1, $(2k+1)^2-1 = 4k^2 +4 = 8q$

From 2, $4k^2 + 12k + 9 -1 = 4k^2+4k+8k+8 = 8q+8k+8$ which is divisible by 8.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.