# Prove divisibility, mathematical induction

#### Jaroslav

I'm still learning English, had to use dictionary and translator, so I'm sorry if its unclear, i will try to explain it more if needed.

1. Homework Statement
For n belonging to N when n is even and n > 3, prove that
(4^(n-3) + 5^(n-3) + 9) is divisible by 9

2. Homework Equations
3. The Attempt at a Solution

P(n) = 4^(n-3) + 5^(n-3)+9
for n = 4 :
P(4) = 4^1 + 5^1 + 9 = 18, divisible by 9

Now assume that n=k, P(k) = 4^(k-3) + 5^(k-3)+9 is div by 9, then solve it for P(k+2) = 4^(k-1) + 5^(k-1)+9

And here is the problem, i know that i should use assumption from n=k, but i really don't know how. I have problem with rearranging things to involve it...this is what i tried to use somehow, but always get stuck without any clear step forward
4^(k-3) + 5^(k-3)+9 = 4^(-2)*4^(k-1)+5^(-2)*5^(k-1)+9 = 9m
Somehow i wanted to get that (k-1) exponent from it, but i cant deal with multipliers there

Related Precalculus Mathematics Homework Help News on Phys.org

#### Fightfish

You should be working the other way around: try to rewrite P(k+2) in terms of quantities that you know are divisible by $9$. Here's a good starting point: $4^{k-1} + 5^{k-1} = 16\left(4^{k-3}\right) + 25 \left(5^{k-3}\right)$
and note that by our inductive hypothesis, $4^{k-3} + 5^{k-3}$ is divisible by $9$.

#### PeroK

Homework Helper
Gold Member
2018 Award
I'm still learning English, had to use dictionary and translator, so I'm sorry if its unclear, i will try to explain it more if needed.

1. Homework Statement
For n belonging to N when n is even and n > 3, prove that
(4^(n-3) + 5^(n-3) + 9) is divisible by 9

2. Homework Equations
3. The Attempt at a Solution

P(n) = 4^(n-3) + 5^(n-3)+9
for n = 4 :
P(4) = 4^1 + 5^1 + 9 = 18, divisible by 9

Now assume that n=k, P(k) = 4^(k-3) + 5^(k-3)+9 is div by 9, then solve it for P(k+2) = 4^(k-1) + 5^(k-1)+9

And here is the problem, i know that i should use assumption from n=k, but i really don't know how. I have problem with rearranging things to involve it...this is what i tried to use somehow, but always get stuck without any clear step forward
4^(k-3) + 5^(k-3)+9 = 4^(-2)*4^(k-1)+5^(-2)*5^(k-1)+9 = 9m
Somehow i wanted to get that (k-1) exponent from it, but i cant deal with multipliers there
First, the question seems strange, as the $+9$ isn't doing anything and why start with $n = 4$ then use $n-3$? Why not just start with $n = 1$ and prove it for odd $n$?

Anyway, have you thought of using $mod \ 9$?

#### Jaroslav

First, the question seems strange, as the $+9$ isn't doing anything and why start with $n = 4$ then use $n-3$? Why not just start with $n = 1$ and prove it for odd $n$?
The task is more complicated, at start i had a story about hero who fights a hydra, and each "round" he cut off all her heads, except black, and after that more heads of different colours grow up. Long story short, after little programming and some assuming i made this formula and domain of a function myself. 9 is number of black heads that can not be cut down, and i start at n = 4 because its first round when number of head is divisible by 9

#### PeroK

Homework Helper
Gold Member
2018 Award
The task is more complicated, at start i had a story about hero who fights a hydra, and each "round" he cut off all her heads, except black, and after that more heads of different colours grow up. Long story short, after little programming and some assuming i made this formula and domain of a function myself. 9 is number of black heads that can not be cut down, and i start at n = 4 because its first round when number of head is divisible by 9
Well, perhaps don't worry about that! See post #2.

#### Jaroslav

and note that by our inductive hypothesis, $4^{k-3} + 5^{k-3}$ is divisible by $9$.
Hypotesis is that 4k−3+5k−3 + 9 is div by 9, so i want to ask, is it mathematicaly correct to assume that (number divisible by 9) + 9 is still divisible by 9? I know it might sound stupid, but our math proffesor is really...i can't find a word for it, just if i do any little mistake or something which is ilogical, i will be eaten alive.
And if yes, can i just write it without that 9? Or should i point it out somehow. Thanks for starting point anyway, I think I'm getting it now.

#### Fightfish

is it mathematicaly correct to assume that (number divisible by 9) + 9 is still divisible by 9?
There is no need to assume - it is a given fact (that if you want to be rigorous, follows from division being right-distributive over addition and subtraction i.e. $(a+b)/c = a/c + b/c$). Just let (number divisible by 9) be some integer multiple $\lambda$ of 9 and clearly adding 9 to it results in a multiple of 9.

#### PeroK

Homework Helper
Gold Member
2018 Award
Hypotesis is that 4k−3+5k−3 + 9 is div by 9, so i want to ask, is it mathematicaly correct to assume that (number divisible by 9) + 9 is still divisible by 9? I know it might sound stupid, but our math proffesor is really...i can't find a word for it, just if i do any little mistake or something which is ilogical, i will be eaten alive.
And if yes, can i just write it without that 9? Or should i point it out somehow. Thanks for starting point anyway, I think I'm getting it now.
If a number is divisible by $9$ and you add or subtract $9$ then the result is divisible by $9$.

A useful way to express divisibility - in this case by $9$ - is:

$n$ is divisible by $9$ if and only if $n = 9k$ for some integer $k$

You could use this to prove the statement above formally.

#### Jaroslav

Thank you, both of you really helped me to solve this, now i just add some small details and homework is complete :)

### Want to reply to this thread?

"Prove divisibility, mathematical induction"

### Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving