Mathematical induction

T

trdada

New member
Joined
Dec 4, 2020
Messages
5
Hi, i have a problem to solve as soon as possible, the question is: Prove that for every n ∈ ℕ number 11 ∙ 3^n + 3 ∙ 7^n - 6 is divisible by 8.
I did the first and second step but the third is where i got stuck. This is what i did in the third:
8|11 x 3^(k+1) + 3 x 7^(k+1) - 6
8|11 x 3^k x 3 + 3 x 7^k * 7 - 6 .............................[edited]

Can someone please help me solve it to the end? thanks.
 
Last edited by a moderator:
trdada said:
Hi, i have a problem to solve as soon as possible, the question is: Prove that for every n ∈ ℕ number 11 ∙ 3^n + 3 ∙ 7^n - 6 is divisible by 8.
I did the first and second step but the third is where i got stuck. This is what i did in the third:
8|11 x 3^(k+1) + 3 x 7^(k+1) - 6
8|11 x 3^k x 3 + 3 x 7^k * 7 - 6 .............................[edited]

Can someone please help me solve it to the end? thanks.
Click to expand...
I am assuming that you are trying to prove the conjecture by "induction".

Since the conjecture is claimed for every n ∈ ℕ number, first, you need to show that the conjecture is true for n = 0.
 
trdada said:
Hi, i have a problem to solve as soon as possible, the question is: Prove that for every n ∈ ℕ number 11 ∙ 3^n + 3 ∙ 7^n - 6 is divisible by 8.
I did the first and second step but the third is where i got stuck. This is what i did in the third:
Click to expand...
Don't forget that \(0\in N\). So we have \(11\cdot 3^0+3\cdot 7^0-6=11+3-6=8\)
The base case is true. Suppose \(K\in N~,~K>0,~\&~8\left|(11\cdot 3^K+3\cdot 7^K-6)\right.\)
Lets look at \(11\cdot 3^{K+1}+3\cdot 7^{K+1}-6)\). Can you use the fact it is true for \(K\) to take the next step, \(K+1~?\)
 
Please please do not write x for times. At this point in your math studies x is a variable.

Proving this by induction is not necessarily the only way. That is in the future do not start your post in the middle of the proof as if we know which method you are using

11 * 3^k * 3 + 3 * 7^k * 7 - 6 = 3(11 ∙ 3^k + 3 ∙ 7^k - 6) + 12*7^k + 12 = 3(11 ∙ 3^k + 3 ∙ 7^k - 6) + 12(7^k + 1). Now show that 7^k + 1 is always even
 
I think the title suggests that it is to be proved by induction.

Following on from what pka said (although he meant [MATH] K \ge 0[/MATH]), the next thing to do is to reduce the K+1 case to something directly related to the K case.

[MATH]11 * 3^{(K+1)} + 3 * 7^{(K+1)} - 6 =\\ 3 * 11 * 3^K + 7 * 3 * 7^K - 6 =\\ 3 * 11 * 3^K + 3 * 3 * 7^K - 18 + 12 + 4 * 3 * 7^K =\\ 3(11 * 3^K + 3 * 7^K - 6) + 12(1 + 7^K).[/MATH]Now what?
 
IMG_20201204_214847.jpg

Yes it is by induction
So someone did this but how do I get to this point 3 x (11 x 3^k+ 3 x 7^k - 6) + 12 x 7^k + 12
Can someone split this row into 2 rows and explain how to do it? Many thanks.
 
We want express the K+1 case in terms of the K case because we know the proposition to be proved is true in the case of K. Does that make sense?

[MATH]11 * 3^{(K+1)} + 3 * 7^{(K+1)} - 6 = 11* 3 * 3^K + 3 * 7 * 7^K - 6. [/MATH]
We have the exponents reduced to what we need for the K case, but we are not there yet. Moreover, the terms still do not quite look like the ones in the K case. If we fix that, we get

[MATH]3(11 * 3^K) + 7(3 * 7^K) + 1(-6).[/MATH]
We have all the right terms, 11 * 3^K, 3 * 7^K, and - 6, but the coefficients are not the same. Now we must think. How can we turn our expression into one related to the K case? We need to have the same coefficient for all those terms. We can choose any of the coefficients to become our standard. I chose 3.

[MATH](1)(-6) = (3 -2)(-6) = 3(- 6) - (2)(- 6) = 3(- 6) + 12.[/MATH]
[MATH]7(3 * 7^K) = (3 + 4)(3 * 7^K) = 3(3 * 7^K) + 12 * 7^K.[/MATH]
The algebra is basic. What is a bit hard is to see the purpose. We are trying to get to something that is as close to the K case as possible.

[MATH]3(11 * 3^K) + 7(3 * 7^K) + 1(-6) = 3(11 * 3^K) + 3(3 * 7^K) + 12 * 7^K + 3(-6) + 12 =\\ 3(11 *3^K + 3 * 7^K - 6) + 12(7^K + 1).[/MATH]The algebra is first year stuff. The question is why we do it. The answer is that we now have the K+1 case expressed in a way that permits us to use what we we know about the K case.

HOW DO WE DO USE THAT INFORMATION?
 
JeffM said:
We want express the K+1 case in terms of the K case because we know the proposition to be proved is true in the case of K. Does that make sense?

[MATH]11 * 3^{(K+1)} + 3 * 7^{(K+1)} - 6 = 11* 3 * 3^K + 3 * 7 * 7^K - 6. [/MATH]
We have the exponents reduced to what we need for the K case, but we are not there yet. Moreover, the terms still do not quite look like the ones in the K case. If we fix that, we get

[MATH]3(11 * 3^K) + 7(3 * 7^K) + 1(-6).[/MATH]
We have all the right terms, 11 * 3^K, 3 * 7^K, and - 6, but the coefficients are not the same. Now we must think. How can we turn our expression into one related to the K case? We need to have the same coefficient for all those terms. We can choose any of the coefficients to become our standard. I chose 3.

[MATH](1)(-6) = (3 -2)(-6) = 3(- 6) - (2)(- 6) = 3(- 6) + 12.[/MATH]
[MATH]7(3 * 7^K) = (3 + 4)(3 * 7^K) = 3(3 * 7^K) + 12 * 7^K.[/MATH]
The algebra is basic. What is a bit hard is to see the purpose. We are trying to get to something that is as close to the K case as possible.

[MATH]3(11 * 3^K) + 7(3 * 7^K) + 1(-6) = 3(11 * 3^K) + 3(3 * 7^K) + 12 * 7^K + 3(-6) + 12 =\\ 3(11 *3^K + 3 * 7^K - 6) + 12(7^K + 1).[/MATH]The algebra is first year stuff. The question is why we do it. The answer is that we now have the K+1 case expressed in a way that permits us to use what we we know about the K case.

HOW DO WE DO USE THAT INFORMATION?
Click to expand...

Wow really nice job, thank you so much!!!
 
You must log in or register to reply here.
Top