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$
6
  • $\begingroup$ $4k+4=4(k+1)$ and $k+1$ is even by assumption. $\endgroup$
    – symplectomorphic
    Commented Mar 6, 2015 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
    Commented Mar 6, 2015 at 17:57
  • $\begingroup$ @symplectomorphic but k could be 3, meaning 4(3) or 12 and 12 isn't divisible by 8. $\endgroup$
    – committedandroider
    Commented Mar 6, 2015 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
    Commented Mar 6, 2015 at 18:06
  • 1
    $\begingroup$ @KimJongUn Thanks great supreme leader :) $\endgroup$
    – committedandroider
    Commented Mar 6, 2015 at 18:09

5 Answers 5

Reset to default
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.

$\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.

$\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.

$\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$.

$\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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .