Proof by induction

Printable View

• October 15th 2007, 10:24 PM
frostking2
Proof by induction
I need to prove 11^n - 6 is divisible by 5 for all n >or = to 1 by induction.
So I start by basis step 11^1 -6 get 5 and 5 is divisible by 5 so basis step is true.

Then I am suppose to add n +1 to both sides and show it is still true.

I am stumped!!! Anyone willing to help a very old and confused student???!!!
• October 16th 2007, 03:35 AM
Plato
Here is the basic trick.
$11^{N + 1} - 6 = \left( {11^{N + 1} - 6 \cdot 11} \right) + \left( {6 \cdot 11 - 6} \right) = 11\left( {11^N - 6} \right) + \left( {6 \cdot 11 - 6} \right)$
• October 16th 2007, 06:03 AM
frostking2
Plato, Thank you for your time and effort on my last two threads. This subject is not like any other I have tackled and I really appreciate your assisitance!!!!
• October 16th 2007, 06:52 AM
topsquark
Quote:

Originally Posted by frostking2
I need to prove 11^n - 6 is divisible by 5 for all n >or = to 1 by induction.
So I start by basis step 11^1 -6 get 5 and 5 is divisible by 5 so basis step is true.

Then I am suppose to add n +1 to both sides and show it is still true.

I am stumped!!! Anyone willing to help a very old and confused student???!!!

Here's another way.

You've got the base case so I'll continue from there.

Let $11^k - 6$ be divisible by 5 for some positive integer k. Then we may define:
$11^k - 6 = 5x$
where x is some positive integer.

We wish to show that $11^{k + 1} - 6$ is divisible by 5. So:
$11^{k + 1} - 6 = 11 \cdot 11^k - 6$

Now recall that $11^k - 6 = 5x$
So
$11^k = 5x + 6$

Thus
$11^{k + 1} - 6 = 11 (5x + 6) - 6$

$= 55x + 66 - 6$

$= 55x + 60$

$= 5(11x + 12)$

Since x is an integer, so is 11x + 12. Thus etc.

-Dan
• October 16th 2007, 08:46 AM
Soroban
Hello, frostking2!

Another approach . . .

Quote:

Prove by induction: . $11^n - 6$ is divisible by 5 for all $n \geq 1$

Verify $S(1)\!:\;\;11^1 - 6 \:=\:5$ . . . True!

Assume $S(k)\!:\;\;11^k - 6 \:=\:5a$ for some integer $a.$

Add ${\color{blue}10\!\cdot11^k}$ to both sides: .**

. . ${\color{blue}10\!\cdot\!11^k} + 11^k - 6 \;=\;{\color{blue}10\!\cdot\!11^k} + 5a$

. . $(10 + 1)\!\cdot\!11^k - 6 \;=\;10\!\cdot11^k + 5a$

. . $11\!\cdot\!11^k - 6 \;=\;10\!\cdot\!11^k + 5a$

. . $11^{k+1} - 6 \;=\;5\underbrace{\left(2\!\cdot\!11^k + a\right)}_{\text{an integer}}$

Therefore: . $11^{k+1}-6$ is divisible by 5.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

**

How did I know what to add? . . . Simple!

I want: . $11^k - 6 + {\color{red}X} \;=\;11^{k+1}-6$

. . Then: . ${\color{red}X} \;=\;11^{k+1} - 11^k \;=\;11^k(11 - 1)$

Therefore: . ${\color{red}X} \:=\:10\cdot11^k$ . . . . see?

• October 18th 2007, 07:15 PM
frostking2
Soroban and Physics Maestro,

Thanks so much for your time and effort. Each time someone explains a little differently I am able to understand it better. I am so glad you are willing to help! Have a great weekend.