Hello sir. I enjoy mathematics and I enjoy watching your videos. You are very good at teaching. I also love Jesus and I like that you spread the word. God bless you sir. ❤️
I tried todo some manipulation. 3^n + 7^n - 2 Let us turn the 3^n to 2(3^n) - 3^n = 2(3^n) - 3^n + 7^n - 2 And regroup = 7^n - 3^n + 2(3^n) - 2 Now I want to use an identity where a^n - b^n = (a-b) (a^n-1 + ... + b^n-1) Another way to see it is that a-b divides a^n - b^n by using the factor theorem and letting a^n - b^n be a polynomial in a and letting a = b. So: = (7 - 3)(7^n-1 + .... + 3^n-1) + 2(3^n - 1) = (7 - 3)(7^n-1 + .... + 3^n-1) + 2( (3-1) (3^n-1 + ... + 1)) = 4(7^n-1 + .... + 3^n-1) + 2(2)(3^n-1 + ... + 1) = 4(7^n-1 + .... + 3^n-1) + 4(3^n-1 + ... + 1) = 4p + 4q = 4(p+q) = divisible by 4. Hence, it is divisible for n greater than or equal to 0. If it's concerning, then we can also just say the identity holds for n >= 1, and then n = 0 is "obvious" because the expression is 0, and 0 divides any number. So it applies for n >= 0
@@StudyOnly-nn1xb I assume they mean integers. If you raise an integer to an irrational/non-integer power, you will most certainly not get an integer and hence there is no meaninful way to talk about "divisible by 4."
@@StudyOnly-nn1xb I think it is usually assumed that the inputs of n are integers, because divisibility problems only work with integers. For example you could sya that 4^2 and 4^3 are divisible by 4, but you wouldn't say the same for 4^pi ot 4^0.5. Either ways, the question SHOULD specific that n is the set of positive integers inclusive of 0, Z+ U {0}. Hope this clarifies.
@@itsphoenixingtimeYou're right, but the problem SHOULD NOT clarify that, it is extremely obvious, just like saying you should put the "2" in the square root. I mean, if you want to do it, no problem, but it's not necessary.
Great video! The advantage of modular arithmetic approavh is that we can generate infinitely many relations like this: 4 divides (3+4u)^n + (7+4v)^n - 2 u, v being integers.
This was a really good way of explaining! I was about to use logarithms (I just recently found out about it) but didn't know what to do, so I watched your explanation - and it was very simple!
I had some trouble with proof by M.I as I'm new to it. I was behind in my class. Luckily I found your videos a while back and now I'm much more confident with proof. You've taught me more than my teachers so I can't thank you enough. Keep making these brilliant videos ❤
I love the modular proof. Great video. By the way, what is the music to your intro? It sounds Jamaican. Very nice, I always enjoy your videos. Math can be fun!
I was trying to avoid using induction here because it was too easy. I like the modular arithmetic here, although that alternative property probably needs an induction proof itself. The approach I am trying involves converting 3 to 4-1 and 7 to 8-1 and fiddling with Pascal's triangle. Edit: I just figured it out. Every term except the last one for (4-1)^n and (8-1)^n is a multiple of 4. The last term for even n is 1. Taking away 2 leaves only the multiples of 4. The last term for odd n is -1. Taking away 2 leaves a -4 along with the multiples of 4.
The 7 and 3 being equally congruent mod 4 is easier to visualize when you consider that both 3 and 7 are congruent to -1 (mod 4), which you then take powers of and alternating between 1 and -1, and -1 (mod 4) is equivalent to 3 (mod 4).
"when you consider that both 3 and 7 are congruent to -1 (mod 4)" I pointed that out already in the comment section to the last video, where the question which is answered here was posted. ;)
@@spy_44_ exactly, like me - who are not blind towards the great Indian people who appreciate, teach and contribute to mathematics, even today, the ones who do not use disrespectful words going to extent saying "nobody appreciates maths & science in india", the ones who try to learn from all people, disregarding nation, gender or any other form of discrimination.
MI is a great way to prove this kind of problem. A limitation is that it only works in problems with discrete domains, it never works for problems with continuous domains
I would go by binomial expansion 3^n+7^n-2=(4-1)^n+(8-1)^n-2 can't write sigma notation in comments section sadly But each term except last one from both binomials is of the form Choose(n,k)*4^(n-k)*(-1)^k or choose(n,k)*8^(n-k)*(-1)^k so everything divides by 4. Now what is left for discussion are just the last terms when n=k so we are left to check if (-1)^n+(-1)^n-2 is divisible by 4 If n=even the term evaluates to 0 divisible by 4 If N=odd the last term evaluates to -4 which is also divisible by 4 qed
I used binomial expansion as well 3^n+7^n-2=3^n+(4+3)^n-2= 3^n+ n £i=0 (n\k)4^k*3^(n-k)-2= 2(3^n-1)+n£i=1(n/k)4^k*3^(n-k) One can write 3^n-1= (3-1) n£i=1*3^(n-i) So we can write 4(n£i=1(3^(n-i)+(n/k)4^(k-1)*3(n-k))
The second method is interesting, I didn't know about it before. It would be nice to prove more strictly that the remainder of the division of 3^n and 7^n alternates between 1 and 3.
Since 3 and 7 are equivalent mod 4, their powers will be as well, so we only need to look at one of them. But 3 and 7 are also equivalent to -1 (mod 4) so we just need to look at powers of -1 (mod 4), which clearly alternate between -1 and +1 (mod 4), or equivalently, 3 and 1.
By using modulo maths, (pretend that the equal sign is actually the congruent sign) 3=-1[4] So 3^n is congruent to either -1 or 1 depending on the parity of n 7=-1[4] so 7^n is also congruent to either -1 or 1 depending on the parity of n And them together : 3^n+7^n=-2[4] (either -2 or 2) Take away 2 from both sides and for the -2 case, notice that -4=0[4] There you go
Goes to show there is always more than 1 way to prove a statement in mathematics. I have a request: by any chance are you able to talk about transfinite induction? I encountered it in my set theory class but apart from that, I don't really see anyone explaining it correctly. Thanks!
Base case: let n = 1 3 + 7 - 2 = 8 = 2*4, thus P(1) is true Now, assume that 4 divides 3^k + 7^k - 2 for some k, k ∈ Z+ Thus, 3^k + 7^k - 2 = 4A for some A, A ∈ Z+ Now sub k + 1 in for n. Our statement becomes P(k+1) = 3^(k+1) + 7^(k+1) - 2 P(k+1) = 3*3^k + 7*7^k - 2 We assumed that 3^k + 7^k - 2 = 4A. Hence, 3^k = 4A - 7^k + 2. -> P(k+1) = 3(4A - 7^k +2) + 7*7^k - 2 P(k+1) = 12A - 3*7^k + 7*7^k + 4 P(k+1) = 12A + (7 - 3)7^k + 4 P(k+1) = 12A + 4*7^k + 4 P(k+1) = 4(3A + 7^k + 1) If k is an integer, then 7^k is also an integer. As such, the sum 3A + 7^k + 1 is demonstrably an integer, showing that since P(k+1) is four times said sum, P(k+1) is also divisible by four. Thus, since our base case is true, and since P(k) -> P(k+1) is true, P(n) must be true for all n, n ∈ Z+.
Because we're writing a general statement that a number is divisible by 4. For example, in some definitions you may consider -4 to be divisible by 4, so m=-1, If that's unacceptable, still 0 is divisible by 4, and 0 isn't included in natural numbers, though whole numbers will work. in this case 3^k+7^k-2>0 , Still we're writing in general so we use Z.
Started with f(n) = 3^n + 7^n - 2 Case n = 0: f(0) = 3^0 + 7^0 - 2 f(0) = 1 + 1 - 2 f(0) = 0 f(0) = 0 (mod 4) Therefore f(0) is divisible by 4. Assume f(n) is divisible by for for all 0
Nice video! But when using modular arithmetic wouldn't you need to actually prove that 3^n and 7^n are congruent to 1 (mod 4) for all even n and to 3 (mod 4) for all odd n?
"wouldn't you need to actually prove that 3^n and 7^n are all divisible by 4 as well?" Err - no? They aren't divisible by 4 on their own. Only the sum 3^n + 7^n - 2 is divisible by 4.
@@bjornfeuerbacher5514 I misspoke. I meant "prove that 3^n and 7^n are 1 (mod 4) for all even n and 3 (mod 4) for all odd n". Edited original comment to correct.
3^n + 7^n - 2 = 3^n + (3+4)^n -2 (3+4)^n = 3^n + 4^n + some combination of strictly positives powers of 3 and 4. 4^n is divisible by 4 and any combinations and 3 and 4 contains 4 meaning it's divisible by 4. So 3^n + 7^n - 2 = 3^n + 3^n - 2 mod 4 = 2 * (3^n -1) mod 4 (3^n is odd so (3^n -1) is even and could thus be replaced by 2k) =4k mod 4 =0 mod 4
I tried using mathmatical induction 'cause I'm more used to it first try the first natural number, n=0 1+1-2=0 which is divisible by 4 now, suppose that it works for a natural m, so 3^m + 7^m - 2 = 4k, k is a nutural number then, let's see if it works to n=m+1 3^m+1 + 7^m+1 -2 = 3.3ˆm + 7.7ˆm -2 =3.3ˆm + (3+4)7ˆm -2 =3( 7ˆm + 3ˆm) + 4.7ˆm -2 = 3.4k+6 + 4.7ˆm -2 =4(3k+1+7ˆm) which is obviously divisible by 4
3^x + 5^x will be divisible by 4 for any odd values of x. 5^x + 7^x will be divisible by 4 for any odd values of x 5^x + 9^x will be NOT divisible by 4 for any value of x. It is more generalized problem.
divisibility is better understood as = 0 mod divisor. so we will look at 0 mod 4 for this equation. technically this is also not equal but congruent, but i do not know the how to write the equal sign with three lines in a browser.
4 l (3^n + 7^n - 2) 4 l (3^n + (3 + 4)^n - 2) (3 + 4)^n = nC0 4^n × 3^0 + nC1 4^(n-1) × 3^1 + ... + nCn 4^0 × 3^n Only the last term, which is 3^n, isn't divisible by 4. 4 l 3^n + 3^n - 2 = 4 l 2(3^n - 1) 3^n - 1 is divisible by 2. The reason why this is always true is because 3 is an odd integer and an odd integer that raised to any integer power gives an odd integer. And an odd integer minus an odd integer gives an even integer. Let 3^n - 1 = 2M 4 l 2 × 2M 4 l 4M
I believe I have a better method. Write 3 as 4-1) and 7 as(8-1). Expand the number of- (4-1)^2 is 4^2-4*2+1 etc. similar with 8-1. Every term is divisible by 4 except the 1 on the end. If n is positive it will be plus 1 if negative it will be minus. Add these to the minus 2 and the answer will be 0 or mins 4. Obviously both are divisible by 4.
@nimaalz4513 its like an expansion technique ig. 7^n = (3+4)^n = 3^n + 4×n×3^n-1... till.4^n. You can search it up, i don't think I will be able to do a good job in explaining it
The point is, this expression is divisible by 8, not just by 4. Care to prove? It seems easy, with the use of residues. Consider first n=2k (even case). Then our expression is 9^k + 49^k -2. Since 9=49=1(mod 8), the result is immediate. Now let n=2k+1 (odd). We have 3×9^k + 7×49^k -2 = 3+7-2 = 0 (mod 8). So the result is immediate as well. I wonder if it is possible to do it without the residues.
In the expansion of the binomial (a+b)^n, all terms are divisible by a, except possibly the last term. Instead of 9^k mod 8, take (8+1)^k and expand it using the binomial theorem.
Well, my induction looked like this: 3*3^n + 7*7^n -2 = (4-1)*3^n + (8-1)*7^n-2+4-4 = 4*3^n + 8*7^n - 4 - (3^n + 7^n -2) Since every part is divisible by 4, the whole thing is divisible by 4.
@@PrimeNewtons My thoughts followed this course. (-1)mod 4= 3 mod 4=7 mod4 so we can substitute ((-1)mod 4)^n+ ((-1) mod 4)^n -2 mod4=0 (-1)^n+(-1)^n=2mod4 For even n we get 1+1=2 for odd n we get (-1-1)mod4=2 Sir, forgive me please I would gladly create films as beautiful as yours, but I lack the ability.
Allow me to spill your secret of catching viewers from one of your subscriber 😅 but it's all because of your captivating voice 😂❤ because once we open your videos it never gets bore instead it becomes more interesting anyway keep going and hoping to see you reaching 1m subscriber ❤️. POV : Bring some challenging topics 👍
If 3^n +7^n -2 =4m Then 2= 3^k+7^k-4m From this hypothesis I have 3^k+1+7^k+1 -(3^k+7^k-4m) Which simplifies to 4m +2(3^k +3*7^k) 3^K +3*7^K IS divisible by 4 Great sir!!!
n=0 1+1-2 = 0 , 4|0 Assume that statement is true for n=k >= 0 Check if assumption implies true statement for successor of k 3^{k+1}+7^{k+1} - 2 = 3*3^{k}+7*7^{k} - 2 3^{k+1}+7^{k+1} - 2 = 3*(3^{k} + 7^{k} - 2) + 4*7^{k}+4 3^{k+1}+7^{k+1} - 2 = 3*(3^{k} + 7^{k} - 2) + 4(7^{k} + 1) 3^{k} + 7^{k} - 2 is divisible by 4 by assumption , 4(7^{k} + 1) is divisible by 4 because 7^{k} + 1 is natural number and is multiplied by 4
For the Mathematical Induction Proof, I understand that assuming 3^k + 7^k - 2 = 4m is crucial, but why can we make that assumption? If we were proving by contradiction, I get why we could make a claim and then prove it doesn't hold true.
Because we want to show that if it is true for n=k then it is also true for n=k+1. Having done this, and since we have shown it is true for n=0 , we have a chain of reasoning that shows the statement’s truth for all values of n.
Making an assumption is always a valid move in the game of proofs. Every proof starts with some set of assumptions. If you make an assumption during a proof, you are starting a new subproof within your proof where you are operating under your initial assumptions as well as the new assumption you just introduced. For induction, your goal is to show that some statement P(n) is true over some range of integer values for n. In this video, the statement P(n) is defined as: there exists an integer m such that 3^n + 7^n - 2 = 4m. We want to prove that P(n) is true for all n≥0. The base case P(0) is shown to be true. A couple more cases, P(1) and P(2), are checked and confirmed as well. We wonder if this chain of true statements continues. We can't exhaustively check all of the infinite cases though. We'll have to stop up to some case P(k). Can we prove that the next case P(k+1) must be true regardless of what value of k we stopped at? To do so, you assume P(k) and show that P(k+1) follows. If you do so, you've proved that if P(k) is true, then P(k+1) is true for arbitrary k≥0. So even though we only checked cases up to P(2), we can be sure that P(3) also holds, and so we can be sure that P(4) holds, etc.
@@jonathanwarwick1117 That's just it though - "IF" it is true for n=k. We haven't actually proved that. We can show n=k+1 just fine if we assume it is true for n=k. But how do we prove n=k is true?
First. Can i have a pin? I'm your biggest fan and you helped me a lot with my homework
Man your pacing for teaching stuff is unbelieveable. It would be a literal dream if you would teach olympiad stuff.
Hello sir. I enjoy mathematics and I enjoy watching your videos. You are very good at teaching. I also love Jesus and I like that you spread the word. God bless you sir. ❤️
I tried todo some manipulation.
3^n + 7^n - 2
Let us turn the 3^n to 2(3^n) - 3^n
= 2(3^n) - 3^n + 7^n - 2
And regroup
= 7^n - 3^n + 2(3^n) - 2
Now I want to use an identity where a^n - b^n = (a-b) (a^n-1 + ... + b^n-1)
Another way to see it is that a-b divides a^n - b^n by using the factor theorem and letting a^n - b^n be a polynomial in a and letting a = b.
So:
= (7 - 3)(7^n-1 + .... + 3^n-1) + 2(3^n - 1)
= (7 - 3)(7^n-1 + .... + 3^n-1) + 2( (3-1) (3^n-1 + ... + 1))
= 4(7^n-1 + .... + 3^n-1) + 2(2)(3^n-1 + ... + 1)
= 4(7^n-1 + .... + 3^n-1) + 4(3^n-1 + ... + 1)
= 4p + 4q
= 4(p+q) = divisible by 4.
Hence, it is divisible for n greater than or equal to 0.
If it's concerning, then we can also just say the identity holds for n >= 1, and then n = 0 is "obvious" because the expression is 0, and 0 divides any number. So it applies for n >= 0
But what 0.5 or values between 0 and 1
@@StudyOnly-nn1xb I assume they mean integers. If you raise an integer to an irrational/non-integer power, you will most certainly not get an integer and hence there is no meaninful way to talk about "divisible by 4."
@@itsphoenixingtime oh I got confused as n€integer or natural wasnt mentioned in question
@@StudyOnly-nn1xb I think it is usually assumed that the inputs of n are integers, because divisibility problems only work with integers. For example you could sya that 4^2 and 4^3 are divisible by 4, but you wouldn't say the same for 4^pi ot 4^0.5.
Either ways, the question SHOULD specific that n is the set of positive integers inclusive of 0, Z+ U {0}.
Hope this clarifies.
@@itsphoenixingtimeYou're right, but the problem SHOULD NOT clarify that, it is extremely obvious, just like saying you should put the "2" in the square root. I mean, if you want to do it, no problem, but it's not necessary.
Great video! The advantage of modular arithmetic approavh is that we can generate infinitely many relations like this:
4 divides (3+4u)^n + (7+4v)^n - 2
u, v being integers.
This was a really good way of explaining! I was about to use logarithms (I just recently found out about it) but didn't know what to do, so I watched your explanation - and it was very simple!
I had some trouble with proof by M.I as I'm new to it. I was behind in my class. Luckily I found your videos a while back and now I'm much more confident with proof. You've taught me more than my teachers so I can't thank you enough. Keep making these brilliant videos ❤
I love the modular proof. Great video.
By the way, what is the music to your intro? It sounds Jamaican. Very nice, I always enjoy your videos. Math can be fun!
Awesome video, would love to see more videos with different modular arithmetic properties, especially for Olympiad mathematics.
Love from Eswatini 💙
I was trying to avoid using induction here because it was too easy. I like the modular arithmetic here, although that alternative property probably needs an induction proof itself.
The approach I am trying involves converting 3 to 4-1 and 7 to 8-1 and fiddling with Pascal's triangle.
Edit: I just figured it out. Every term except the last one for (4-1)^n and (8-1)^n is a multiple of 4. The last term for even n is 1. Taking away 2 leaves only the multiples of 4. The last term for odd n is -1. Taking away 2 leaves a -4 along with the multiples of 4.
That works too. I've seen that in the comments
The 7 and 3 being equally congruent mod 4 is easier to visualize when you consider that both 3 and 7 are congruent to -1 (mod 4), which you then take powers of and alternating between 1 and -1, and -1 (mod 4) is equivalent to 3 (mod 4).
And then you should only observe that +2=-2 mod(4) to conclude the assertion.
"when you consider that both 3 and 7 are congruent to -1 (mod 4)"
I pointed that out already in the comment section to the last video, where the question which is answered here was posted. ;)
@@bjornfeuerbacher5514 You may also observe that 3² = 7² = 1 mod(8). Hence easily conclude that the expression is in fact divisible by 8, not just 4.
@@sobolzeev Thanks for pointing that out. :)
Fabulous! Good explanations of both and great revision if I ever needed to use again
Respect from India because in today's time nobody appreciates Maths and Science. It's like nightmare to UA-camrs or reel masters😅!🙏
Yes, but don't say nobody, there are few ones.
@justnowi8967 bro/sis/uncle who so ever you are. It wasn't for people like you!🙏
@@spy_44_ exactly, like me - who are not blind towards the great Indian people who appreciate, teach and contribute to mathematics, even today, the ones who do not use disrespectful words going to extent saying "nobody appreciates maths & science in india", the ones who try to learn from all people, disregarding nation, gender or any other form of discrimination.
I loved the modulus method
MI is a great way to prove this kind of problem. A limitation is that it only works in problems with discrete domains, it never works for problems with continuous domains
There is induction for all reals but its a bit more difficult
Thank you! Couldn't watch the video earlier i was very occupied with some school stuff but ty
Another method is to use binomial expansion. Have 3^n as (4 - 1)^n and 7^k as (8 -1) ^k.
I just did this.
I would go by binomial expansion
3^n+7^n-2=(4-1)^n+(8-1)^n-2 can't write sigma notation in comments section sadly
But each term except last one from both binomials is of the form Choose(n,k)*4^(n-k)*(-1)^k or choose(n,k)*8^(n-k)*(-1)^k so everything divides by 4.
Now what is left for discussion are just the last terms when n=k so we are left to check if (-1)^n+(-1)^n-2 is divisible by 4
If n=even the term evaluates to 0 divisible by 4
If N=odd the last term evaluates to -4 which is also divisible by 4 qed
I used binomial expansion as well 3^n+7^n-2=3^n+(4+3)^n-2= 3^n+ n £i=0 (n\k)4^k*3^(n-k)-2= 2(3^n-1)+n£i=1(n/k)4^k*3^(n-k)
One can write 3^n-1= (3-1) n£i=1*3^(n-i)
So we can write 4(n£i=1(3^(n-i)+(n/k)4^(k-1)*3(n-k))
The second method is interesting, I didn't know about it before. It would be nice to prove more strictly that the remainder of the division of 3^n and 7^n alternates between 1 and 3.
Since 3 and 7 are equivalent mod 4, their powers will be as well, so we only need to look at one of them. But 3 and 7 are also equivalent to -1 (mod 4) so we just need to look at powers of -1 (mod 4), which clearly alternate between -1 and +1 (mod 4), or equivalently, 3 and 1.
Watching keenly ❤
Wow, It was really interesting!
So cool and easy to understand!!
By using modulo maths, (pretend that the equal sign is actually the congruent sign)
3=-1[4]
So
3^n is congruent to either -1 or 1 depending on the parity of n
7=-1[4] so 7^n is also congruent to either -1 or 1 depending on the parity of n
And them together :
3^n+7^n=-2[4] (either -2 or 2)
Take away 2 from both sides and for the -2 case, notice that -4=0[4]
There you go
I must add (even though it's obvious) that the power of 3^n and 7^n is gonna be the same, hence why you'll get either -2 or 2 when adding
Great video prime newtons!
Goes to show there is always more than 1 way to prove a statement in mathematics.
I have a request: by any chance are you able to talk about transfinite induction? I encountered it in my set theory class but apart from that, I don't really see anyone explaining it correctly. Thanks!
Base case: let n = 1
3 + 7 - 2 = 8 = 2*4, thus P(1) is true
Now, assume that 4 divides 3^k + 7^k - 2 for some k, k ∈ Z+
Thus, 3^k + 7^k - 2 = 4A for some A, A ∈ Z+
Now sub k + 1 in for n. Our statement becomes
P(k+1) = 3^(k+1) + 7^(k+1) - 2
P(k+1) = 3*3^k + 7*7^k - 2
We assumed that 3^k + 7^k - 2 = 4A. Hence,
3^k = 4A - 7^k + 2.
->
P(k+1) = 3(4A - 7^k +2) + 7*7^k - 2
P(k+1) = 12A - 3*7^k + 7*7^k + 4
P(k+1) = 12A + (7 - 3)7^k + 4
P(k+1) = 12A + 4*7^k + 4
P(k+1) = 4(3A + 7^k + 1)
If k is an integer, then 7^k is also an integer. As such, the sum 3A + 7^k + 1 is demonstrably an integer, showing that since P(k+1) is four times said sum, P(k+1) is also divisible by four. Thus, since our base case is true, and since P(k) -> P(k+1) is true, P(n) must be true for all n, n ∈ Z+.
One question: at 3:17 m belongs to Z which includes also the negative number. Why Z and not just N?
Because we're writing a general statement that a number is divisible by 4.
For example, in some definitions you may consider -4 to be divisible by 4, so m=-1,
If that's unacceptable, still
0 is divisible by 4, and 0 isn't included in natural numbers, though whole numbers will work.
in this case 3^k+7^k-2>0 ,
Still we're writing in general so we use Z.
Started with f(n) = 3^n + 7^n - 2
Case n = 0:
f(0) = 3^0 + 7^0 - 2
f(0) = 1 + 1 - 2
f(0) = 0
f(0) = 0 (mod 4)
Therefore f(0) is divisible by 4.
Assume f(n) is divisible by for for all 0
Nice video!
But when using modular arithmetic wouldn't you need to actually prove that 3^n and 7^n are congruent to 1 (mod 4) for all even n and to 3 (mod 4) for all odd n?
"wouldn't you need to actually prove that 3^n and 7^n are all divisible by 4 as well?"
Err - no? They aren't divisible by 4 on their own. Only the sum 3^n + 7^n - 2 is divisible by 4.
@@bjornfeuerbacher5514 I misspoke. I meant "prove that 3^n and 7^n are 1 (mod 4) for all even n and 3 (mod 4) for all odd n".
Edited original comment to correct.
Very nice application of method of mathematical induction. ❤from India.
Very nice.
Shouldn't the question also indicate that the result of the division should be a whole number for clarity's sake?
3^n + 7^n - 2 = 3^n + (3+4)^n -2
(3+4)^n = 3^n + 4^n + some combination of strictly positives powers of 3 and 4.
4^n is divisible by 4 and any combinations and 3 and 4 contains 4 meaning it's divisible by 4.
So
3^n + 7^n - 2 = 3^n + 3^n - 2 mod 4
= 2 * (3^n -1) mod 4
(3^n is odd so (3^n -1) is even and could thus be replaced by 2k)
=4k mod 4
=0 mod 4
Thanks Sir
I tried using mathmatical induction 'cause I'm more used to it
first try the first natural number, n=0
1+1-2=0 which is divisible by 4
now, suppose that it works for a natural m, so
3^m + 7^m - 2 = 4k, k is a nutural number
then, let's see if it works to n=m+1
3^m+1 + 7^m+1 -2
= 3.3ˆm + 7.7ˆm -2
=3.3ˆm + (3+4)7ˆm -2
=3( 7ˆm + 3ˆm) + 4.7ˆm -2
= 3.4k+6 + 4.7ˆm -2
=4(3k+1+7ˆm) which is obviously divisible by 4
Can we do it by binomial theorem of (1+x)^n manipulation?
you forgot to mention that n is an integer
3^x + 5^x will be divisible by 4 for any odd values of x.
5^x + 7^x will be divisible by 4 for any odd values of x
5^x + 9^x will be NOT divisible by 4 for any value of x.
It is more generalized problem.
divisibility is better understood as = 0 mod divisor. so we will look at 0 mod 4 for this equation. technically this is also not equal but congruent, but i do not know the how to write the equal sign with three lines in a browser.
Wonderful presentation. Loved every moment of this.
3 and 7 each equal -1 mod 4, so 3^n and 7^n are (-1)^n mod 4. For n even, get 1+1-2=0 mod4, for n odd get -1-1-2= -4= 0 mod 4.
4 l (3^n + 7^n - 2)
4 l (3^n + (3 + 4)^n - 2)
(3 + 4)^n = nC0 4^n × 3^0 + nC1 4^(n-1) × 3^1 + ... + nCn 4^0 × 3^n
Only the last term, which is 3^n, isn't divisible by 4.
4 l 3^n + 3^n - 2 = 4 l 2(3^n - 1)
3^n - 1 is divisible by 2. The reason why this is always true is because 3 is an odd integer and an odd integer that raised to any integer power gives an odd integer. And an odd integer minus an odd integer gives an even integer.
Let 3^n - 1 = 2M
4 l 2 × 2M
4 l 4M
For even n=2m, 3^n + 7^n = 3^2m + 7^2m = (3^2)^m + (7^2)^m = 9^m + 49^m = 1^m + 1^m mod 4 ie 1+1=2 mod 4.
For odd n = 2m+1, 3^n + 7^n = 3.1^m + 7.1^m mod 4 ie 3+7 = 10 = 2 mod 4.
I believe I have a better method. Write 3 as 4-1) and 7 as(8-1). Expand the number of- (4-1)^2 is 4^2-4*2+1 etc. similar with 8-1. Every term is divisible by 4 except the 1 on the end. If n is positive it will be plus 1 if negative it will be minus. Add these to the minus 2 and the answer will be 0 or mins 4. Obviously both are divisible by 4.
We can also use binomial theorem by taking 2 cases - n is even and odd
whats binomial theorem ?
@nimaalz4513 its like an expansion technique ig. 7^n = (3+4)^n = 3^n + 4×n×3^n-1... till.4^n.
You can search it up, i don't think I will be able to do a good job in explaining it
The point is, this expression is divisible by 8, not just by 4. Care to prove? It seems easy, with the use of residues. Consider first n=2k (even case). Then our expression is
9^k + 49^k -2. Since 9=49=1(mod 8), the result is immediate. Now let n=2k+1 (odd). We have
3×9^k + 7×49^k -2
= 3+7-2 = 0 (mod 8). So the result is immediate as well.
I wonder if it is possible to do it without the residues.
In the expansion of the binomial (a+b)^n, all terms are divisible by a, except possibly the last term.
Instead of 9^k mod 8, take (8+1)^k and expand it using the binomial theorem.
can you prove that the 3^n power is always equal to 1 mod 4 and 3 mod 4 repeating ?
It's easy to prove
@@PrimeNewtons how?
Just prove for n is even by mathematical induction. Then prove for n is odd by multiplying by 3.
I believe that solving this with Chinese remainder theorem may lead to a quicker solution, though your approach is more witty
3^n + 7^n - 2 = (4 - 1)^n + (8 - 1)^n - 2 = > expands to powers of 4 using binomial theorem because the 1 + 1 - 2 cancels or becomes 1 + 1 + 2 = 4....
11:38
you meant to write 7^n here since 7 = 3 (mod 4) only
👍
(7^n/2+1)(7^n/2-1)+(3^n/2+1)(3^n/2-1) each term can be divisible by 2
Well, my induction looked like this:
3*3^n + 7*7^n -2 =
(4-1)*3^n + (8-1)*7^n-2+4-4 =
4*3^n + 8*7^n - 4 - (3^n + 7^n -2)
Since every part is divisible by 4, the whole thing is divisible by 4.
Wow
Make a video proofing n⁴-6n³+23n²-18n + 24 is divisible by 24 for every n ≥ 0
Just do: 3 = 4-1 and 7 = 8-1. (4-1)^n + (8-1)^n = 2 mod 4 trivial
You don't want to make a UA-cam video this way. You wouldn't be helping many people. Your skill level is for a select group.
@@PrimeNewtonsHowever, you can get a better result this way. Actually, your expression is divisible by 8, not just 4.
@@PrimeNewtons My thoughts followed this course.
(-1)mod 4= 3 mod 4=7 mod4
so we can substitute
((-1)mod 4)^n+ ((-1) mod 4)^n -2 mod4=0
(-1)^n+(-1)^n=2mod4
For even n we get
1+1=2
for odd n we get
(-1-1)mod4=2
Sir, forgive me please
I would gladly create films as beautiful as yours, but I lack the ability.
@@sobolzeev (-1)^n mod 4 is easy to calculate , and that is the idea behind this solution.
@@boguslawszostak1784 Try n=2k, 2k+1. 3²=7²=1 mod (8)
Allow me to spill your secret of catching viewers from one of your subscriber 😅 but it's all because of your captivating voice 😂❤ because once we open your videos it never gets bore instead it becomes more interesting anyway keep going and hoping to see you reaching 1m subscriber ❤️. POV : Bring some challenging topics 👍
3=4-1, 7=8-1, just expand the terms and you prove it, easy
Incredible!
If 3^n +7^n -2 =4m
Then 2= 3^k+7^k-4m
From this hypothesis I have 3^k+1+7^k+1 -(3^k+7^k-4m)
Which simplifies to 4m +2(3^k +3*7^k)
3^K +3*7^K IS divisible by 4
Great sir!!!
No, your third line simplifies to 4m + 2. The (k + 1) exponents must be inside grouping symbols.
Nice
Glad I'm first here
n=0
1+1-2 = 0 , 4|0
Assume that statement is true for n=k >= 0
Check if assumption implies true statement for successor of k
3^{k+1}+7^{k+1} - 2 = 3*3^{k}+7*7^{k} - 2
3^{k+1}+7^{k+1} - 2 = 3*(3^{k} + 7^{k} - 2) + 4*7^{k}+4
3^{k+1}+7^{k+1} - 2 = 3*(3^{k} + 7^{k} - 2) + 4(7^{k} + 1)
3^{k} + 7^{k} - 2 is divisible by 4 by assumption , 4(7^{k} + 1) is divisible by 4 because 7^{k} + 1 is natural number and is multiplied by 4
7 should b 7^n at bottom of left panel in method 2.
also can show if x=y mod w then x^n = y^n mod w. otherwise, good presentation, PN.
Spell out the word "be."
For the Mathematical Induction Proof, I understand that assuming 3^k + 7^k - 2 = 4m is crucial, but why can we make that assumption? If we were proving by contradiction, I get why we could make a claim and then prove it doesn't hold true.
Because we want to show that if it is true for n=k then it is also true for n=k+1. Having done this, and since we have shown it is true for n=0 , we have a chain of reasoning that shows the statement’s truth for all values of n.
Making an assumption is always a valid move in the game of proofs. Every proof starts with some set of assumptions. If you make an assumption during a proof, you are starting a new subproof within your proof where you are operating under your initial assumptions as well as the new assumption you just introduced.
For induction, your goal is to show that some statement P(n) is true over some range of integer values for n. In this video, the statement P(n) is defined as: there exists an integer m such that 3^n + 7^n - 2 = 4m. We want to prove that P(n) is true for all n≥0. The base case P(0) is shown to be true. A couple more cases, P(1) and P(2), are checked and confirmed as well. We wonder if this chain of true statements continues. We can't exhaustively check all of the infinite cases though. We'll have to stop up to some case P(k). Can we prove that the next case P(k+1) must be true regardless of what value of k we stopped at? To do so, you assume P(k) and show that P(k+1) follows. If you do so, you've proved that if P(k) is true, then P(k+1) is true for arbitrary k≥0. So even though we only checked cases up to P(2), we can be sure that P(3) also holds, and so we can be sure that P(4) holds, etc.
@@jonathanwarwick1117 That's just it though - "IF" it is true for n=k. We haven't actually proved that. We can show n=k+1 just fine if we assume it is true for n=k. But how do we prove n=k is true?
@@crossflux971 But we have proved it’s true for the base case n=0. Therefore it is true for n=1. Since it’s true for n=1, it must be true for n=2 etc.
@jonathanwarwick1117 I'm still not following. Why does the Base case of n=0 prove that n=1 also holds true?
Don't you need to specify, up front, that n is in *Z* ?