Prove divisibility, mathematical induction

In summary, the student is still learning English and had to use a dictionary and translator to complete the homework. The student attempted to solve the equation but is having difficulty with rearranging things to involve the assumption. The student has come up with a solution using modulus 9.
  • #1
Jaroslav
4
0
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
 
Physics news on Phys.org
  • #2
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##.
 
  • Like
Likes Jaroslav and PeroK
  • #3
Jaroslav said:
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##?
 
  • #4
PeroK said:
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
 
  • #5
Jaroslav said:
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.
 
  • #6
Fightfish said:
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.
 
  • #7
Jaroslav said:
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.
 
  • Like
Likes Jaroslav
  • #8
Jaroslav said:
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.
 
  • Like
Likes Jaroslav
  • #9
Thank you, both of you really helped me to solve this, now i just add some small details and homework is complete :)
 

1. What is divisibility?

Divisibility is a mathematical concept that refers to the ability to divide one number by another without any remainder. In other words, one number is divisible by another if the division results in a whole number.

2. How can I prove divisibility?

The most common way to prove divisibility is by using the division algorithm, which states that for two integers a and b, there exists unique integers q and r such that a = bq + r, where 0 ≤ r < b. If r is equal to 0, then a is divisible by b.

3. What is mathematical induction?

Mathematical induction is a proof technique used to prove a statement for all natural numbers. It involves two steps: the base case, where the statement is shown to be true for the first natural number, and the inductive step, where it is shown that if the statement is true for a certain natural number, it is also true for the next natural number.

4. How do I use mathematical induction to prove divisibility?

To use mathematical induction to prove divisibility, you must first state the statement you want to prove, such as "for all n, if n is a multiple of 3, then n^2 is also a multiple of 3". Then, you must show that the statement is true for the base case, which in this example would be n = 3. Finally, you must show that the statement holds for the inductive step, which in this example would involve showing that if the statement is true for n, it is also true for n+1.

5. What are some examples of using mathematical induction to prove divisibility?

Some examples of using mathematical induction to prove divisibility include proving that every power of 2 is divisible by 3, that every prime is either 2 or a product of two odd numbers, and that the sum of the first n odd numbers is equal to n^2. These proofs use the principles of mathematical induction and the properties of divisibility to establish the truth of the statements for all natural numbers.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
5
Views
939
  • Precalculus Mathematics Homework Help
Replies
6
Views
769
  • Precalculus Mathematics Homework Help
Replies
3
Views
1K
  • Precalculus Mathematics Homework Help
Replies
2
Views
888
  • Precalculus Mathematics Homework Help
Replies
9
Views
1K
  • Precalculus Mathematics Homework Help
Replies
3
Views
592
  • Precalculus Mathematics Homework Help
Replies
10
Views
738
  • Precalculus Mathematics Homework Help
Replies
4
Views
770
  • Precalculus Mathematics Homework Help
Replies
17
Views
2K
  • Precalculus Mathematics Homework Help
Replies
4
Views
690
Back
Top