• Support PF! Buy your school textbooks, materials and every day products via PF Here!

Prove divisibility, mathematical induction

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
 
954
116
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

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
9,528
3,511
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##?
 
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

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
9,528
3,511
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.
 
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.
 
954
116
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

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
9,528
3,511
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.
 
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" You must log in or register to reply here.

Related Threads for: Prove divisibility, mathematical induction

Replies
3
Views
1K
Replies
3
Views
2K
Replies
2
Views
4K
Replies
2
Views
5K
  • Posted
2
Replies
31
Views
1K

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
Top