1. ## induction

prove by induction:

10^n+1 + 3.10^n + 5 is a multiple of 9, ∀n ∈ ℕ

2. ## Re: induction

Originally Posted by beast
prove by induction:

10^n+1 + 3.10^n + 5 is a multiple of 9, ∀n ∈ ℕ
Base case is easy. So assume we know the theorem is true for some n = k. That means
$10^{k + 1} + 3 \cdot 10^k + 5 = 9m$
where m is some integer.

We need to show that
$10^{k + 2} + 3 \cdot 10^{k + 1} + 5$
is divisible by 9.

To this end, solve the "k" equation for 10^{k+1}
$10^{k + 1} = -3 \cdot 10^k - 5 + 9m$

Multiply both sides by 10 so you get that
$10^{k + 2} = -3 \cdot 10^{k+1} - 50 - 9m$

Plug this into your "k + 1" case.

-Dan

3. ## Re: induction

thanks but im new to this so i don't understand what your saying.
my lecturer does not teach well. :/

4. ## Re: induction

Originally Posted by topsquark
Base case is easy. So assume we know the theorem is true for some n = k. That means
$10^{k + 1} + 3 \cdot 10^k + 5 = 9m$
where m is some integer.

We need to show that
$10^{k + 2} + 3 \cdot 10^{k + 1} + 5$
is divisible by 9.

To this end, solve the "k" equation for 10^{k+1}
$10^{k + 1} = -3 \cdot 10^k - 5 + 9m$

Multiply both sides by 10 so you get that
$10^{k + 2} = -3 \cdot 10^{k+1} - 50 - 9m$

Plug this into your "k + 1" case.

-Dan
Okay. First: Do you understand why 9m appears in the first line? Do you understand how I derived the 10^(k + 2) expression in the last line?

-Dan

5. ## Re: induction

i understand the 9m but i dont get the 10 ^ (k+2)

6. ## Re: induction

Originally Posted by topsquark
$10^{k + 2} + 3 \cdot 10^{k + 1} + 5$
is divisible by 9.

To this end, solve the "k" equation for 10^{k+1}
$10^{k + 1} = -3 \cdot 10^k - 5 + 9m$

Multiply both sides by 10 so you get that
$10^{k + 2} = -3 \cdot 10^{k+1} - 50 - 9m$

Plug this into your "k + 1" case.
We have
$10^{k + 1} = -3 \cdot 10^k - 5 + 9m$
from the n = k assumption.

Now multiply both sides by 10:
$10 \cdot 10^{k + 1} = -30 \cdot 10^k - 50 + 90m$

I'm going to reset m to be such that 90m --> 9m. (I suppose I should change the variable to "a" so that 90m = 9a or something.)

$10^{k + 2} = -3 \cdot 10^{k + 1} - 50 + 9m$

You need to show that
$10^{k + 2} + 3 \cdot 10^{k + 1} + 5$
is divisible by 9. Plug the above expression into this line.

-Dan

7. ## Re: induction

ok i now understand the k+2 part
my lecturer never thought us that.

im now lost after this part:

I'm going to reset m to be such that 90m --> 9m. (I suppose I should change the variable to "a" so that 90m = 9a or something.)

10^{k + 2} = -3 \cdot 10^{k + 1} - 50 + 9m

You need to show that
10^{k + 2} + 3 \cdot 10^{k + 1} + 5
is divisible by 9. Plug the above expression into this line.

8. ## Re: induction

$10^{k + 2} = -3 \cdot 10^{k + 1} - 50 + 9m$

So
$10^{k + 2} + 3 \cdot 10^{k + 1} + 5$

$= \left ( -3 \cdot 10^{k + 1} - 50 + 9m \right ) + 3 \cdot 10^{k + 1} + 5$

Is this divisible by 9?

-Dan

9. ## Re: induction

i honestly dont know...
there are some students in my class who are repeating this course for the 3rd time :/
can you please do the entire sum and explain it line by line. that would really help. the induction divisibility questions give me alot of trouble.
what are some tips on how to do them?
I appreciate any help rendered.

10. ## Re: induction

You want the end result to be $9(\text{expression that evaluates to an integer})$. Nine times an integer is a multiple of nine. So, topsquark gave you the solution. Just simplify and factor out a nine.

11. ## Re: induction

how do i simplify and factor out 9?

12. ## Re: induction

Simplify means combine like terms. You factor out a nine by dividing each remaining term by 9.

13. ## Re: induction

would it be 3.10^(k+1) -45 + 9m is divisible by 9?

14. ## Re: induction

What happened to the $-3\cdot 10^{k+1}$?

It is difficult to assist you when you are not familiar with the process of simplifying expressions. I recommend a thorough review of algebra.

15. ## Re: induction

Originally Posted by beast
prove by induction:
10^n+1 + 3.10^n + 5 is a multiple of 9, ∀n ∈ ℕ
Lets start over. $P(n)=10^{n+1}+3\cdot 10^n+5$.
We want to show that $P(n)$ is a multiple of nine for each positive integer $n$.

To get going look at $P(1)=135$ which is a multiple of nine( the digit sum is 9).

Lets say for positive integer $K\ge 1$ and we know that $P(K)=10^{K+1}+3\cdot 10^K+5$ is a multiple of nine.

The next one up is $P(K+1)$. So lets look at it.

$P(K+1)=10^{K+2}+3\cdot 10^{K+1}+5=10(\underbrace {{{10}^{K + 1}} + 3 \cdot {{10}^K} + 5}_{\text{multiple of nine}})-45$ is that correct?
Now we have the difference of two multiples of nine.

So from any point we have shown that the next one up works.
We know $P(1)$ is a multiple of nine so $P(2)$ is a multiple of nine.
We just keep going through all positive integers.

Page 1 of 2 12 Last