Proof by induction

**frostking2** · October 15th 2007, 10:24 PM

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???!!!

**Plato** · October 16th 2007, 03:35 AM

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

**frostking2** · October 16th 2007, 06:03 AM

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!!!!

**topsquark** · October 16th 2007, 06:52 AM

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

**Soroban** · October 16th 2007, 08:46 AM

Hello, frostking2!

Another approach . . .

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?

**frostking2** · October 18th 2007, 07:15 PM

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.

Thread: Proof by induction

LinkBack

Thread Tools

Display

Proof by induction

Similar Math Help Forum Discussions

Proof by Induction

Proof by Induction

Mathemtical Induction Proof (Stuck on induction)

Proof by Induction??

Proof with algebra, and proof by induction (problems)

Search Tags