Proof via mathematical induction

[UOAMCBURGER]

Homework Statement

Use mathematical induction to prove that (8n − 7n − 1) is divisible by 49 for any n ∈ N.

Correction by mentor for better readability: $49\,|\,(8^n-7n-1)$

The Attempt at a Solution

We can see that the base case is satisfied here:
n = 1,
8^1-7*1-1 = 0 and 49 | 0 is true since 49 | 0 => 49*a = 0 where a is an integer, here a = 0.
therefore base case is proven
Inductive assumption is : Assume true : 49 | (8^k -7k - 1) for n=k
Now have to show that 49 | (8^k+1 - 7k - 8)

So we can see that 8^k+1 - 7k - 8 = 8*8^k -7k -1, but I am unsure of where to go from here.
Any help will be appreciated.

 

[fresh_42]

Homework Statement

Use mathematical induction to prove that (8n − 7n − 1) is divisible by 49 for any n ∈ N.[/B]

The Attempt at a Solution

We can see that the base case is satisfied here:
n = 1,
8^1-7*1-1 = 0 and 49 | 0 is true since 49 | 0 => 49*a = 0 where a is an integer, here a = 0.
therefore base case is proven
Inductive assumption is : Assume true : 49 | (8^k -7k - 1) for n=k
Now have to show that 49 | (8^k+1 - 7k - 8)

So we can see that 8^k+1 - 7k - 8 = 8*8^k -7k -1, but I am unsure of where to go from here.
Any help will be appreciated.

Is it $8\,|\,(8n-7n-1)$ or $8\,|\,(8^n-7n-1)\,$? But in either case you have to increment both occurrences of $n\,.$ It's often useful to start at the end and transform $(8(n+1)-7(n+1)-1)$ or $(8^{n+1}-7(n+1)-1)$ depending on which version is the one claimed.

 

[UOAMCBURGER]

Is it $8\,|\,(8n-7n-1)$ or $8\,|\,(8^n-7n-1)\,$? But in either case you have to increment both occurrences of $n\,.$ It's often useful to start at the end and transform $(8(n+1)-7(n+1)-1)$ or $(8^{n+1}-7(n+1)-1)$ depending on which version is the one claimed.

whoops it is 8ⁿ not 8n

 

[UOAMCBURGER]

whoops it is 8ⁿ not 8n

also sort of a side note, i know if we can get the LHS:
(8(n+1)−7(n+1)−1) to be of the form 49*(...) which is obviously just a multiple of 49 then it is shown to be divisible by 49, but does this apply for the factors of 49 also? i.e., if I can get that LHS into the form 7*(...) where it is some multiple of 7 and 7 is a factor of 49 is that enough to prove that it can be divisible by 49 or does that principle only apply to the form a(..b..) where a | b and we can get b into a multiple of a form.

 

[fresh_42]

also sort of a side note, i know if we can get the LHS:
(8(n+1)−7(n+1)−1) to be of the form 49*(...) which is obviously just a multiple of 49 then it is shown to be divisible by 49, but does this apply for the factors of 49 also? i.e., if I can get that LHS into the form 7*(...) where it is some multiple of 7 and 7 is a factor of 49 is that enough to prove that it can be divisible by 49 or does that principle only apply to the form a(..b..) where a | b and we can get b into a multiple of a form.

If you have a number $N$ which is divisible by $7$, then $N=7r$ for some integer. However, you still need $7\,|\,r\,.$

Edit: $\operatorname{gcd}(7,7)=7$ so you really need that $49$ is a divisor. If you have two different primes $p$ and $q$, then it is sufficient to show $p\,|\,N$ and $q\,|\,N$ to conclude $(p\cdot q)\,|\,N\,.$


As a sidenote: You want to have a look on https://www.physicsforums.com/help/latexhelp/ which makes formulas a lot better to read.

Let me summarize: We want to show $49 = 7^2 \,|\, (8^n+7n-1)$ for all $n\in \mathbb{N}$.
It clearly holds for $n=1$ and we assume that $49 = 7^2 \,|\, (8^n+7n-1)$. Maybe we will need that it holds for all numbers up to $n$, that depends on the proof. Both can be assumed as introduction hypothesis. Now we have to show that
$$
49 = 7^2\,|\, (8^{n+1}+7({n+1})-1)
$$
Is this correct? It seems to be wrong, if I check $n=2$.

As said, start at the end and see where it goes. We have $8^{n+1}+7{n+1}-1=8\cdot 8^n +7n +6$ and this has to be brought into a form, to which the induction hypothesis can be applied.

 

[UOAMCBURGER]

If you have a number $N$ which is divisible by $7$, then $N=7r$ for some integer. However, you still need $7\,|\,r\,.$

As a sidenote: You want to have a look on https://www.physicsforums.com/help/latexhelp/ which makes formulas a lot better to read.

Let me summarize: We want to show $49 = 7^2 \,|\, (8^n+7n-1)$ for all $n\in \mathbb{N}$.
It clearly holds for $n=1$ and we assume that $49 = 7^2 \,|\, (8^n+7n-1)$. Maybe we will need that it holds for all numbers up to $n$, that depends on the proof. Both can be assumed as introduction hypothesis. Now we have to show that
$$
49 = 7^2\,|\, (8^{n+1}+7({n+1})-1)
$$
Is this correct? It seems to be wrong, if I check $n=2$.

As said, start at the end and see where it goes. We have $8^{n+1}+7{n+1}-1=8\cdot 8^n +7n +6$ and this has to be brought into a form, to which the induction hypothesis can be applied.

Sorry, not sure when the 8ⁿ-7*n became + 7*n but what we have to show is: 49 = 7² | (8ⁿ⁺¹ - 7*n -1), hence n=2 clearly holds since 49 is divisible by itself.

 

[fresh_42]

Sorry, not sure when the 8ⁿ-7*n became + 7*n but what we have to show is: 49 = 7² | (8ⁿ⁺¹ - 7*n -1), hence n=2 clearly holds since 49 is divisible by itself.

Just add ## before and after your formulas and it will be a lot clearer.
$n=1:\quad 8^{n+1}-7n-1=64-7-1=56$
$n=2:\quad 8^{n+1}-7n-1=512-14-1=497$
There must be something wrong.

I guess it is $8^n-7n-1$ or $8^{n+1}-7(n+1)-1$

Hint: Use $8^n-1=(8-1)\cdot (8^{n-1}+8^{n-2}+\ldots +8^2+8^1+1)$

 

[UOAMCBURGER]

Sorry, not sure when the 8ⁿ-7*n became + 7*n but what we have to show is: 49 = 7² | (8ⁿ⁺¹ - 7*n -1), hence n=2 clearly holds since 49 is divisible by itself.

Furthermore,

Just add ## before and after your formulas and it will be a lot clearer.
$n=1:\quad 8^{n+1}-7n-1=64-7-1=56$
$n=2:\quad 8^{n+1}-7n-1=512-14-1=497$
There must be something wrong.

I guess it is $8^n-7n-1$ or $8^{n+1}-7(n+1)-1$

ok thanks ill be sure to add them in the future.
Why are you plugging in n=1 and n=2 into what we have to show rather than into the given equation?
We are given the equation with the 8ⁿ and then inductive step is assume that is correct for all n in N.
Then given that assumption, we have to prove that ## 49 = 7² | (8ⁿ⁺¹ -7(n+1) -1) ## for a proof via mathematical induction.

 

[UOAMCBURGER]

also not sure why my ## didn't work

 

[fresh_42]

Furthermore,

ok thanks ill be sure to add them in the future.
Why are you plugging in n=1 and n=2 into what we have to show rather than into the given equation?

Your formula was wrong. If the statement for $n$ is $49\,|\,(8^n-7n-1)$ then the statement for the induction step is $8^{n+1}-7(n+1)-1$. I just checked for $n=1,2$ with your equation and got something wrong. With those I just mentioned it will work.

We are given the equation with the 8ⁿ and then inductive step is assume that is correct for all n in N.
Then given that assumption, we have to prove that ## 49 = 7² | (8ⁿ⁺¹ -7(n+1) -1) ## for a proof via mathematical induction.

Yes, but you wrote $8^{n+1}-7n-1$ which is wrong.

Take $8^{n+1}-7(n+1)-1$ and see if you can structure it in a way such that $8^n-7n-1=49a$ is applicable. The see if the rest is also divisible by $49$, i.e. twice by $7$.

 

[UOAMCBURGER]

Your formula was wrong. If the statement for $n$ is $49\,|\,(8^n-7n-1)$ then the statement for the induction step is $8^{n+1}-7(n+1)-1$. I just checked for $n=1,2$ with your equation and got something wrong. With those I just mentioned it will work.

Yes, but you wrote $8^{n+1}-7n-1$ which is wrong.

Take $8^{n+1}-7(n+1)-1$ and see if you can structure it in a way such that $8^n-7n-1=49a$ is applicable. The see if the rest is also divisible by $49$, i.e. twice by $7$.

Oh right yeah sorry, I can get to the stage where we get ##49=7²|(8*8ⁿ-7n-8)$=>$49a=7²a=8*8ⁿ-7n-8## but unsure of how i can apply the inductive assumption to this?

 

[fresh_42]

Start with $8^{n+1}-7(n+1)-1=8\cdot 8^n -7n -7 -1 =(7+1)\cdot8^n-7n-1-7 = \ldots$ and the induction hypothesis is almost there and for $7\cdot 8^n$ look at my hint in post no.7

 

[FactChecker]

@UOAMCBURGER ,A couple of notes:
1) Please correct the exponent in your post #1 so that others will not get confused.
2) The reason why the LaTex ## didn't work: If the equation has BBcode things like you get from the exponent button above the edit page, LaTex that includes it does not work. After much confusion, I realized what was going on and switched to only using LaTex and never use those buttons.

 

[UOAMCBURGER]

Start with $8^{n+1}-7(n+1)-1=8\cdot 8^n -7n -7 -1 =(7+1)\cdot8^n-7n-1-7 = \ldots$ and the induction hypothesis is almost there and for $7\cdot 8^n$ look at my hint in post no.7

I'm still not sure how i can apply your hint or the inductive assumption, I can get to the step in your post #12 but i don't see how we can express the LHS in terms of a multiple of 7 or would it be 7^2 or does that even matter since you could express 49 as 7a where a = 7 = 7²

 

[UOAMCBURGER]

Start with $8^{n+1}-7(n+1)-1=8\cdot 8^n -7n -7 -1 =(7+1)\cdot8^n-7n-1-7 = \ldots$ and the induction hypothesis is almost there and for $7\cdot 8^n$ look at my hint in post no.7

Okay so I have solved via another method to what you were hinting at (i think)
By the inductive assumption we get:

49t = (8^k-7k-1), therefore 8^k = 49t + 7k + 8

Then we obviously have to show that this holds for k+1, so then:

8^k+1 - 7(k+1) - 1 = 8*8^k - 7k - 8 = 8(49t + 7k + 1) - 7k - 8 = 49(8t) + 56k + 8 -7k -8 = 49(8t+k)

Hence, 49 | (8^k+1 - 7(k+1) - 1)

 

[fresh_42]

I'm still not sure how i can apply your hint or the inductive assumption, I can get to the step in your post #12 but i don't see how we can express the LHS in terms of a multiple of 7 or would it be 7^2 or does that even matter since you could express 49 as 7a where a = 7 = 7²

It's hard to give even more hints and not to solve the problem. The goal is, we have to prove $49\,|\,8^{n+1}-7(n+1)-1$ and only know that $49\,|\,8^{n}-7(n)-1\,.$ So in order to apply what we know, we have to transform $8^{n+1}-7(n+1)-1$ in a way that this knowledge can be applied. Therfore we calculate
$$
8^{n+1}-7(n+1)-1 = 8\cdot 8^n -7n-1-7=(7+1)\cdot 8^n -7n-1-7=(7\cdot 8^n)-(7\cdot 1)+8^n-7n-1=7\cdot (8^n-1) + 49\cdot a
$$
for some $a\in \mathbb{Z}\,.$ What's left to show is $7\,|\,(8^n-1)\,.$

 

[UOAMCBURGER]

It's hard to give even more hints and not to solve the problem. The goal is, we have to prove $49\,|\,8^{n+1}-7(n+1)-1$ and only know that $49\,|\,8^{n}-7(n)-1\,.$ So in order to apply what we know, we have to transform $8^{n+1}-7(n+1)-1$ in a way that this knowledge can be applied. Therfore we calculate
$$
8^{n+1}-7(n+1)-1 = 8\cdot 8^n -7n-1-7=(7+1)\cdot 8^n -7n-1-7=(7\cdot 8^n)-(7\cdot 1)+8^n-7n-1=7\cdot (8^n-1) + 49\cdot a
$$
for some $a\in \mathbb{Z}\,.$ What's left to show is $7\,|\,(8^n-1)\,.$

^^ solved another way, thanks though.

 

[fresh_42]

Okay so I have solved via another method to what you were hinting at (i think)
By the inductive assumption we get:

49t = (8^k-7k-1), therefore 8^k = 49t + 7k + 8

Then we obviously have to show that this holds for k+1, so then:

8^k+1 - 7(k+1) - 1 = 8*8^k - 7k - 8 = 8(49t + 7k + 1) - 7k - 8 = 49(8t) + 56k + 8 -7k -8 = 49(8t+k)

Hence, 49 | (8^k+1 - 7(k+1) - 1)

... or so.

As you saw, my way might be a bit more complicate, but as $(8^n-1)=(8-1)\cdot (8^{n-1}+\ldots +8^0)=7\cdot (\ldots)$ the result is the same.