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.

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

Homework Equations

3. The Attempt at a Solution
[/B]
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 can't deal with multipliers there

 

[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]

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.

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

Homework Equations

3. The Attempt at a Solution
[/B]
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 can't 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]

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 4^k−3+5^k−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]

Hypotesis is that 4^k−3+5^k−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 :)