I'd use this trick: n^3 + 11n = n^3 - n + 12n. n^3 - n = n(n - 1)(n + 1) = (n - 1)*n*(n + 1). Among these three consecutive numbers n-1, n n+1, at least one is even and one is divisible by 3. Therefore their product is divisible by 2 and 3, then it's divisible by 6. 12n is also divisible by 6, so their sum (n^3 - n) + 12n = n^3 + 11n must be also divisible by 6.
I saw the video solution and it is Hella elegant. I am curious if you would try to present the problem to a middle schooler would such an approach help their understanding or just baffle them regarding how were they supposed to think it up. I think the simplest way of looking at it would be considering the ways n can be written with regards to divisibility by 3 : n=3k or n=3k+1 or n=3k+2 with k another integer. If n = 3k then n(n^2+11) is obviously divisible by 3 as n itself is. For the other cases we need to show n^2+11 is divisible by 3. N=3k+1 then n^2+11=9k^2+6k+12 all members of the sum are divisible by 3 so the sum will also be Case n=3k+2 then n^2+11= 9k^2+12k+15 which is also divisible by 3
If you know the Fermat's Little Theorem, we get a third method: n^3 = n (mod 3) then n^3 + 11n = n + 11n = 12n (mod 3) 12n = 3 * 4n = 0 (mod 3) so we proved that the expression is divisible by 3. Jointly with the proof of divisible by 2 explained in the video, we have that the expression is divisible by 6
I think you don’t necessarily need FLT here, just notice that the product of any three consecutive numbers is divisible by 6, thus n(n-1)(n+1)=n^3-n=0 (mod 6). Thus n^3=n (mod 6). So question= n +11n=12n=0 (mod 6).
@@ElVerdaderoAbejorro fermat little theorem in that form is always applicable, n^(p-1) = 1 mod p need (n,p) = 1, but n^p = n mod p is always true, but euler theorem does need (n,6) = 1 though
I think I found shorter proof: Plug (n+1) instead of n: (n+1)^3 + 11(n+1) (n+1)((n+1)^2+11) (n+1)(n^2+2n+12) (n+1)(n(n+2) + 12) n(n+1)(n+2) + 12(n+1) Three consequtive numbers multiplied are always divisible by 6 because there must be a multiple of 2 and a multiple of 3 among them.
@@terracottapie6872 Thanks. I actually just tried standard induction: assuming it works for n, proof for n+1. And when I got the result I realized I never used "since it works for n" part.
Using modular arithmetic (thanks Gauss), all we need is to show that f(n) =: n^3 + 11n is divisible by 6 when n= 0, +-1, +-2, or 3. In fact, since f(-n) = -f(n), we need not check n = -1 or -2.
God, I love how many equally valid ways there are to approach this. In a discipline like Math where everything is connected, it's always like a fun easter egg hunt to find all the ways you can approach a problem.
Holds for n = 0. (n+1)^3 + 11(n+1) = n^3 + 3n^2 + 3n + 1 + 11n + 11 = (n^3 + 11n) + 3(n^2 + n + 4) n odd ==> n^2 odd ==> n^2 + n + 4 even n even ==> n^2 even ==> n^2 + n + 4 even OR n^2 + n + 4 = n(n+1) + 4 even as n(n+1) even, product of 2 consecutive integers so last term divisible by 6, and first term is too by induction hypothesis (And as we want to prove for all integers, we should strictly do the other direction too, that is with n -> n-1. The exact same argument will apply)
I’ve just tried to do like what you suggested when I was watching this video, and found out it is not working right away because it is impossible to show the proposition is true n=k+1 in just one step: you’ll get (k+1)^3 + 11(k+1) = 6N+ 3k^2 + 3k + 12. You can only tell by intuition that 3k^2 + 3k + 12 is only divisible by 3, but not divisible by 6 Then I have to do another M.I. to prove 3k^2 + 3k + 12 is divisible by 6 which turned out to be valid, so it proves the original proposition as well. I have to say my method is not really efficient when compared to that in the video LOL
@@PrimeNewtonsça marche bien, on est amené à montrer que 3n²+3n+12 est divisible par 6 et donc que n²+n+4 est divisible par 2 (soit par une autte récurrence, soit par la parité)
Every integer kann either be written as 3k, 3k+1 or 3k+2 with k being another integer. Plug these into the formula, and every time you get an expression that is a multiple of 3.
You explain the connections so clearly that all I can say is: Respect! Also, you speak at a very good pace, so I can easily follow along even with my average English skills. I'm already looking forward to the next videos! Thank you so much, Joe.
In my opinion, this is the simplest and, most importantly, the most universal method. In this case, you don't even need to substitute all the numbers, because 4 = -2 and 5 = -1, and since our function is odd, it's enough to check 0, 1, and 2
@user-es6hc4qk3t it's not the simplest. If you prove it using mod 2 and mod 3 you can do the math in your head and 0 mod 2 and 0 mod 3 implies 0 mod 6 since 2 and 3 are prime factors
Slightly better method is to note that n^3+11n is even, regardless if n is even or odd. Thus, it suffices to prove that n^3+11n is a multiple of 3 and then we can do the tedious bash but with only 3 cases.
Thank you for your wonderful and blessed videos, which I enjoy very much. Divisibility problems like this one are popular in the UK and the two most commonly used methods are proof by exhaustion and proof by induction. When using either, a minor variation on your approach is not to consider divisibility by 2 and 3 separately but to work with 6 directly. For proof by exhaustion: If n is even, n=2k for some integer k and f(n) = n^3+11n = 8k^3+22k = 8k(k^2-1)+30k = 8k(k-1)(k+1)+30k which is divisible by 6 because 6|30 and 6|k(k-1)(k+1) because three consecutive integers include at least one multiple of 2 and exactly one multiple of 3. If n is odd, n=2k-1 for some integer k and f(n) = n^3+11n = (8k^3+22k) - 3(2k)^2 + 3(2k) -1 - 11 = (8k^3+22k) + 6(-2k^2 + k -2) which is divisible by 6 because 6|6 and the first term is the expression shown to be divisible by 6 in the n even case. For proof by induction: f(1) = 1+11=12 and 6|12 and f(k+1) = f(k) + (f(k+1)-f(k)) which is divisible by 6 because 6 | f(k) by assumption and f(k+1) - f(k) = 3k^2 + 3k + 1 + 11 = 3k(k+1) + 12 which is divisible by 6 because 6|12 and 6| 3k(k+1) because two consecutive integers include exactly one even integer. Like you, I prefer proof by exhaustion. And especially for this problem given that n can be non-positive. Proving divisibility by 6 for f(1) and f(k+1) proves the result only for the natural numbers. I guess this is resolved by proving the result for f(k-1) similarly - this is fine as f(k-1)-f(k) = -3k(k-1) - 12 which is divisible by 6 for the same reasons as given above - so that the dominoes then fall in both directions from f(1) simultaneously. The need for this is avoided by using exhaustion, where the integer k is unrestricted. Again, thank you for your lovely videos and i look forward to seeing the next one. God bless yuu ❤
I could do it in 2 ways: 1. using modular artihmetics, simply show that for n = 1, 2, 3, 4, or 5 this results in a multiple of 6. 2. n^3 + 11n = n^3 -n + 12n. 12n is a multiple of 12 which is a multiple of 6. and n^3 - n is a product of 3 consecutive numbers: (n-1)n(n+1) so there's gotta be an even number and a multiple of 3 in it.
Prove that for any integer n. n^3+11n is divisible by 6. To show that n^3+11n is divisible by 6, we need to show that n^3+11n is n is even and it’s a multiple of 3.
Love your channel ... you combine elegant problem solving skills with a very soothing teaching style. That said, I have to admit that I am bit passed high school ... 68 years young to be exact. All-in-all ... brain food (for geeks!) ...
Your mathematical induction does not complete the proof. It only shows that 3 divides n³+11n if n is a natural number. You could say that if n is negative then n=-j for j is a natural number, and then show that (-j)³+11(-j)=-(j³+11j), and then using your M.I this is also divisible by 3. You would also need to test n=0 to complete the set of integers.
You can also just do the induction step the opposite way. IE if you show that when it's true for k that it's also true for k-1 the same way that you show that it's true for k+1. No need for specifically testing just negative numbers or testing 0 individually, any base case is sufficient to prove it for all integers.
Mathematical induction shows that if it's true for n then it's true for n+1. It's obviously true for 0, therefore it's true for all non-negative integers. And it's likewise obviously true for all integers, since negative integers are just positive integers * -1, and if you multiply a number that's divisible by 3 by an integer (like -1) then the result is also divisible by three.
n^3+11n is divisible by 6 proof by modular arithmetic. Write n as the largest multiple of 6 plus its residu i.e. n = 6a + b where b is an integer between 0 and 5 now work out n^3 + 11n = (6a+b)^3 + 11(6a+b) => (6a)^3 + 3b * (6a)^2 + 3 * 6a * b^2 + b^3 + 11 * 6a + 11b group all the factors with an a in it. ⇒ 6a^3 + 6 * 3ba^2 + 6 * 3 ab^2 + 6 * 11a + b^3 +11b every factor with an a in it, has a factor of 6 associated with it. therefor these factors are always divisible by 6 and can be ignored for the rest of the proof. The remaining factors are: b^3 + 11b. Which is in the same form as our starting question but b is limited in its range to the integers from 0 to 5. These can be easily checked by hand. first rewrite b^3 + 11b to b(b^2+11). for this equation to be divisible by 6 one of the factors needs to be divisible by 6 or one is divisible by 2 and the other is divisible by 3 b | b^2 +11 0 | 11 0 is divisible by 6 ✓ 1 | 12 12 is divisible by 6 ✓ 2 | 15 2 is divisible by 2 and 15 is divisible by 3✓ 3 | 20 20 is divisible by 2 and 3 is divisible by 3✓ 4 | 27 4 is divisible by 2 and 27 is divisible by 3✓ 5 | 36 36 is divisible by 6 ✓ All 6 cases work out. this means that the starting equation is divisible by 6 QED It is a nice starting problem to get into modular arithmetic in my opinion.
Proof using Product of N consecutive integers is divisible by N! (This theorem is also be proved below) Consider product of 3 consecutive integers : (n-1) * (n) * (n+1). This is divisible by 3!, that is by 6, by the above theorem -- (1) (n-1) * (n) * (n+1) = n(n^2-1) = n^3 - n Adding & Subtracting 12n n^3 - n = n^3 - n + 12n - 12n = n^3 + 11n - 12n From (1) n^3 + 11n - 12n is divisible by 6 Since 12n is divisible by 6, it follows that n^3 + 11n should also be divisible by 6 Q.E.D ======================================================================================================= Proof of Product of N consecutive integers is divisible by N! Given the product of 'n' consecutive integers [m-(n-1)]*[m-(n-2)]*[m-(n-3)]...[m-2]*[m-1]*m, prove it is divisible by n! n! = n*(n-1)*(n-2)*(n-3)....3*2*1 Consider the divisibility of [m-(n-1)] term from above product by n Either n divides [m-(n-1)] or it doesn't and leaves a remainder r. If it divides, then there is nothing to prove. If it doesn't, we can write express : [m-(n-1)] = n*k + r. Here 0 < r < n This implies [m-(n-1)] would be divisible by n, if r were to be added to it Notice that the given product has (n-1) consecutive terms excluding [m-(n-1)]. Therefore, by successively incrementing [m-(n-1)] by 1, one of the successive terms in the product would be divisible by n, as the remainder r
1) If n is even n^3 + 11 n =n(n^2+11) is even. 2)if n is odd n^2 is odd [square of odd (odd*odd) is odd] n^2 +11= odd + odd =even n(n^2 +11)= odd *even =even Hence if n is even /odd, n^3 + 11n is even. Hence it is divisible by 2 ** Now 3) If n is a multiple of 3 n^3+11n=n(n^ 2+11) is a multiple of 3 4)if n is not a multiple of 3, then n will leave 1/2 as remainder when it is divided by 3 Hence in this case I) n= 3 k +1 OR ii) n = 3k +2 I) If n =3k +1 n^2+11 =9k^2 +6k +12 =3(3k^2+ 2k +4) is divisible by 3 Hence n^3+11n = n(n^2+11) > n* a number divisible by 3 Hence n^3+11n is divisible by 3 when n is not divisible 3 and leave remainder 1 when n is divided by 3. ii) If n=3k +2 then n^2+11 =9k^2 +12k +15 =3(3k^2+4k+ 5) Hence n^ 2 +11 is divisible by 3 Hence n^3 +11n =n (n^2+11) > n* a number divisible by 3 Hence n^3+11n is divisible by 3 when n is not divisible by 3 and leave remainder 2 when it is divided by 3 Hence n^3+11n is divisible by 3 if n is not divisible by 3 Hence it is proved that n^3+11n is divisible by 2 & 3 and so it is divisible by 2*3 ie 6 Comment please
i like it, but i would use a slightly different approach. first i'd get, that n^3+11n = even (same as everybody does). then, let's look if we can extract 3 somehow. as we see - n is cubed. so, n*(n+1)(n+2) definately gives us divisibility with 3 and cube, what does it lack? >> n(n+1)(n+2) = n (n^2 + 3n +2) = n^3 + 3n^2 + 2n okay, then, let's substract what we had in the beginning, and look of "extra parts": >> n^3 + 3n^2 + 2n - n^3 -11n = 3n^2 - 9n
I found an odd way of proving it: The difference between consecutive whole number cubes is a Σ(6•(0-n))+1, and the difference between consecutive multiples of 11 is, well, 11 Since the equation is a sum I can borrow the +1 from the cube side and tack it onto the 11x side, making the difference between each consecutive solution Σ(6·(0-n))+12 And that is divisible by 6 for every whole number n
I'm nearing 50, but have always been interested in high school math. This caught my attention and I actually watched the whole video. Thanks for posting. Cheers from India.
Lots of alternative proofs in the comments, one I didn’t see is simply “brute forcing” to see the formula is always equal to zero mod 2 and mod 3. Mod 2: Test 0 and 1 0 ³ + 11*0 = 0 mod 2 1 ³ + 11*1 = 12 = 0 mod 2 Mod 3: test -1, 0, and 1 -1 ³ + 11*(-1) = -12 = 0 mod 3 0 ³ + 11*0 = 0 mod 3 1 ³ + 11*1 = 12 = 0 mod 3 So since all possible cases mod 2 and mod 3 equal 0 in those modulos, the formula is also always 0 mod 6.
I'm surprised modular arithmetic wasn't one of the suggested proofs to show that the equation is divisible by 3 n % 3 must be in the set {0, 1, 2}, therefore, if all of these equal 0 when plugged into the equation modulo 3, every value of n is. Case 1: n % 3 = 0 (n^3 + 11n) % 3 = 0*0*0 + 2 * 0 = 0 Case 2: n % 3 = 1 (n^3 + 11n) % 3 = 1*1*1 + 2 * 1 = 1 + 2 = 0 Case 3: n % 3 = 2 (n^3 + 11n) % 3 = 2*2*2 + 2 * 2 = 2 + 1 = 0 Therefore, n^3 + 11n is divisible by 3
I used induction, checking f(1) and then setting f(k) = 6m, and then f(k+1) = 6m + 3k^2 + 3k + 12. This is divisible by three, so you get f(k+1)/3 = 2m+k^2 + k + 4. Set g(n) = n^2+n+4, and prove this is divisible by two by induction. Check g(1), then continue with g(k) = 2t, g(k+1) = 2t + 2k + 2. This is divisible by two, so you get g(k)/2 = t+k+1. Put this back into the original function, and you get f(k+1)/3 = 2m+2t+2k+2. Therefore f(k+1)/6 = m+t+k+1, so f(n) is divisible by 6.
For the divisible by 3 one, I used a different approach, which uses modular arithmetic. So for any integer n in n mod 3 , there will be 3 results, which are 0, 1, and 2 For result 0, substituting it to the original equation gives 0, which is a multiple of 3. For result 1, substituting it gives 12, which is a multiple of 3. And for result 2, substituting it gives 30, which again, is a multiple of 3. Hope this helps :)
n^3+11n = (n^3-n)+12n= n*(n^2-1)+6*(2n) = (n-1)*n*(n+1) + 6*2n The product of three consecutive integers is always divisible by 6, because exactly one of those three is a multiple of three (the other two are 3 mod 1 and 3 mod 2), and either n is even or both n-1 and n+1 are even, so the product is a multiple of 2. Thus, the whole thing is divisible by 6.
You can use induction directly to prove for 6 6m + 3k^2 + 3k +12 = 6m + 3(k^2 + k + 4) Number in brackets is always even so 6m + 3(2n) = 6m + 3*2(n) = 6( m + n)
Method 3: Same argument for divisible by 2. For divisible by 3: There are 3 cases: n mod 3 = 0 n mod 3 = 1 n mod 3 = 2 For n mod 3 = 0: n is divisible by 3, so n(n^2+11) must be too because it has n as a factor. If n mod 3 = 1 or 2, the expression can only be divisible by 3 if n^2+11 is, because the factor n will not have prime factor 3. If n mod 3 = 1, n can be written as 3k-1, with k being an integer as per definition of the modulo operation. (3k-1)^2+11 = 9k^2-6k+1+11 = 3(3k^2 - 2k + 4) which has factor 3 and thus is divisible by 3 If n mod 3 = 2, n = 3k-2, with k an integer. (3k-2)^2+11 = 9k^2-12k+4+11 = 3(3k^2 - 4k + 5) which has factor 3.
Your "Method 2" delves into the theory of Congruences. After a few frustrating failures at solving the problem, I thought I might have to do the same. So I reviewed Congruences in Courant & Robbins and decided it could be done that way - thanks for the demo! But then it struck me that the induction approach might be just as easy, so I tried that instead. I got pretty well as far as you did with P(k) and P(k+1) (except that I kept using 'n'). I then realized that if I worked out what has to be added to P(n) to get P(n+1), and could prove that the added bit evaluates to a multiple of 6, I'd have the proof (since P(1), which is 12, is a multiple of 6). So I went: P(n) = n^3 + 11n P(n+1) = n^3 + 3n^2 + 3n + 1 + 11n + 11. By inspection, the added bit is 3n^2 + 3n + 12, which I wrote as 3n(n + 1) + 12. This is a multiple of 3, but also a multiple of 2 - because n(n+1) is an odd number times an even number, and the '12' at the end is also a multiple of 3x2. Done - QED. In summary, I more or less duplicated your "Method 1", but I demonstrated divisibility by both 3 and 2 in the same line. Quite a neat little problem - I might include it in the book I'm currently writing (any idea who should be acknowledged ?).
Proving divisibility by 3 is simpler if you stick to the same factored form as you used in the 'even' proof. 3 cases: case 1: n is multiple of 3, so can be represented as 3k. So you have (3)(k)(9k² + 11). Is (3)(integer) so divisible by 3. Case 2: n = 3K + 1. Then we have (3k + 1)[(3k + 1)² + 11] which simplifies to (3k + 1)(3)(3k² + 2k + 4). We have (integer)(3)(integer) so divisible by 3. Case 3: n = 3k - 1. Then is (3k - 1)(3)(3k² - 2k + 4) which is also (integer)(3)(integer) so divisible by 3.
This second method was so elegant!!! I didn't see where this was going until you expanded n²-1 to (n-1)(n+1) and when I saw the product of three consecutive numbers, this put a big smile on face. Beautiful! I found the way you used the induction a little strange. Maybe it's the way I was taught. The way I'd do it would be like this: First step is like yours: show that the proposition is true for f(1): 1³+11×1 = 12; 12 is divisible by 3. Actually, we could even have started with f(0): 0³ + 11×0 = 0; 0 is divisible by 3, albeit it looks almost too simple! 😅 The second step is where I took a slightly different approach. I started with the difference f(k+1)-f(k). f(k+1)-f(k) = [(k+1)³ + 11(k+1)] - [k³ + 11k] = [(k³+3k²+3k+1) + 11k+11] - [k³ + 11k] = [here we can cancel k³ and 11k] 3k²+3k+1 + 11 = 3k² + 3k + 12 = 3 (k²+k+4) What we have shown in this second step is that the difference between the value of the function of two consecutive numbers is divisible by 3. The difference to your approach is that I am not assuming, as you've done at 6:38, that f(k) is divisible by 3. I think, if we want to be rigorous, you'd have to be more explicit to show that your assumption was valid. I thought your approach through and see how one can make that case (the algebra of the two approaches is very similar after all) but I would have liked this to be more explicit. Anyway, like I said, we have shown that the difference between the value of f(n) and f(n+1) is divisible by 3, which means that if f(n) is divisible by 3 (which remains to be shown), then f(n+1) will also be divisible by 3. I realize now that I used that theorem from your method 2. 😉 Now step 1 comes into the picture. We know that f(1) is divisible by 3, therefore applying step 2 f(2) is as well. As, since we used mathematical induction, are f(3), f(4), f(5)... all the way up to infinity. It should be noted that technically we aren't finished yet because we only have shown that n³+11n is divisible by 3 for all n≥1 but not n
Induction also works without dividing 6 into its factors. n=1 gives 12. Them set k^3+11k = 6m. k -> k+1 gives 6m+3(k^2+k+4) k^2+k+4 is always even, so call it 2p. Then we have 6(m+p), which is always divisible by 6.
My proof before watching: Let S = n^3 + 11n = n(n^2 + 11) If n is even, then S is even. If n is odd, then n^2 + 11 is an odd number plus an odd number, which is even. So S is even. n must be even or odd, and in both cases S is even. If n is divisible by 3, then S is divisible by 3. If n is not divisible by 3, then n = 3k + 1 or n = 3k + 2 where k is an integer. If n = 3k + 1, then S = (3k + 1)((3k + 1)^2 + 11) = (3k + 1)(9k^2 + 6k + 12) = 3(3k + 1)(3k^2 + 2k + 4), which is divisible by 3. If n = 3k + 2, then S = (3k + 2)((3k + 2)^2 + 11) = (3k + 2)(9k^2 + 12k + 15) = 3(3k + 2)(3k^2 + 4k + 5), which is divisible by 3. n must be either divisible by 3 or not divisible by 3, and in both cases S is divisible by 3. Since S is both divisible by 2 and divisible by 3, it is divisible by 2 * 3 = 6.
Here's my very short proof: In Z/6Z (and all the more in Z/2Z and Z/3Z) we have: n^3 + 11n = n^3 - n = n.(n-1).(n+1) The latter product is 0 in both Z/2Z and Z/3Z since (at least) one of its factors is always 0, no matter what n is. So we know that both 2 and 3 divide n^3 + 11n, and, since 2 and 3 are relative prime (their gcd is 1), 6 must also divide it. q.e.d.
Before watching this video, here's my solution: Base case: n = 0, 0^3+11(0)=0 which is is divisible by 6 Claim: n^3 + 11n is divisible by 6 Proof by induction: (n+1)^3 + 11(n+1) = n^3 + 3n^2 + 3n + 1 + 11n + 11 = n^3 + 3n^2 + 14n + 12 if k + 12 is divisible by 6, k is divisible by 6, therefore we can get rid of the + 12 term -> n^3 + 3n^2 + 14n Since we assume n^3 + 11n is divisible by 6 we can use the same logic and subtract n^3 + 11n -> 3n^2 + 3n = 3n(n+1) n(n+1) is always even since either n or n+1 must be even, thus we can rewrite n(n+1) as 2*a, where a is an integer thus 3n(n+1) = 3*2*a = 6*a QED Hopefully this is valid :)
Product of k consecutive integers is divisible by k!, so (n³-n) is divisible by 6 and 12n is divisible by 6...hence (n³+11n) is divisible by 6... Amazing method and work sir!!
I really like the second method, because it is very elegant and short. Your induction proof however is incomplete because with starting at 1 and the induction step n+1 you have shown this only for positive integer but not for all integer. I approached it a little different. It's more straight forward but also longer. The beginning is the same, so I also proved that n^3+11n is even. Then you can make 3 cases for n: it can be congruent to 0, 1 or 2 mod 3. case 1: 0 => we can write n as n=3k with k being an integer. Therefor n^3+11n=(3k)^3+11*3k=27k^3+33k=3(9k+11k). Therefor the divisibility by 3 is shown for this case as 3 is a factor. case 2: 1 => we can write n as 3k+1 with k being an integer. Therefor we get (3k+1)^3+11(3k+1)=27k^3+27K^2+9k+1+33k+11=3(9k^3+9k^2+14k+4), again 3 is factor and the divisibility by 3 is shown. case 3: 2 => we can write n as 3k+2 with k being an integer. Therefor we get (3k+2)^3+11(3k+2)=27k^3+54k^2+36k+8+33k+22=3(9k^3+18k^2+23k+10) and again 3 is a factor and the divisibility is also shown for this case
I loved this proof! I saw this on my recommended, and I thought: "No way you can prove something like that! Not even any constants to base it upon!" In all honesty, I like the number theory method of proving it better (even though I didn't even know any until now 😁). It turns out I was overthinking the entire way of solving it, I find it intriguing that it was solved mainly using logic, rather than you know, numbers, etc... 😃😃😃
Another method is to calculate the difference between two consecutive terms of the series n^3 + 11n, since (n+1)^3 + 11(n+1) - n^3 - 11n = 3(n^2 + n + 12), we are trying to show that the difference between two terms is a multiple of 6 (and thus prove by induction that all terms are divisible by 6), 6 can be factored into 3 and 2, there is already a 3 in the equation. So the problem is reduced to showing that n^2 + n + 11 is even for all integers n. You can consider the cases when n is even and when n is odd separately to show this. The base case is (1)^3 + 11(1) = 12 which is divisible by 6, so all terms are divisible by 6
n³(mod 6) ≡ n. (I didn't know this, but it takes 20 seconds to check the possibilities.) 11(mod 6) ≡ -1. So [n³ - 11n](mod 6) ≡ n - n = 0. QED. You are a master of patient, crystal-clear descriptions of ludicrously complicated approaches.
You don’t need to check the possibilities. Phi(6) = (2-1)(3-1) = 2. So n^2 = 1 mod 6, and so n^3 = n mod 6. In general, x^phi(m) = 1 mod m so long as x != 0 mod m. (Look up “Euler’s totient function” in Wikipedia) So you have two cases: * n = 0 mod 6, in which case n^3 + 11n = 0 mod 6, trivially * n != 0 mod 6, in which case n^3 + 11n = n^(phi(6) + 1) + (12-1)n = n - n = 0 mod 6.
To see the divisibility by 3, I just consider the following cases: a) n = 0 (mod 3) --> n^3 + 11n = 0 + 0 = 0 (mod 3) b) n = 1 (mod 3) --> n^3 + 11n = 1 + 11 = 12 = 0 (mod 3) c) n = 2 (mod 3) --> n^3 + 11n = 8 + 22 = 30 = 0 (mod 3) This shows that n^3 + 11n is divisible by 3.
Un bel exposé, clair et précis, et une méthode bien choisie. Beau travail. 👍👍 Il existe une solution beaucoup PLUS COURTE (une ligne) que je te propose pour le plaisir. n³+11n = n³ - n + 12n donc 6 divise n³+11n 6 divise n³ - n car 12n est un multiple de 6. Or n³-n = n(n²-1) = (n-1)n(n+1). Produit de 3 nombres consecutifs. donc divisible par 2 et par 3 qui sont premiers entr'eux, donc ce produit est divisible par leur produit qui est 6.😉😉 Si on souhaite faire une démonstration par récurrence, on peut faire directement une récurrence en supposant P(n) divisible par 6. Elle ressemble beaucoup à ce que tu as écrit.
Hi, in your 2nd proof I would find more natural to start with B=(n-1)*n*(n+1) since it's obviously multiple of 3; then choose C=(+ or -)(n^3+11*n) since it can be divisible by 3 regardless of the sign; then compute B+C with both signs and see whether at least one of the sums is multiple of 3 (in this case, choosing "-" yields B+C=-12*n.)
A very simple approach: Since 6 is kind of small number, just build a table of n^3 (mod 6) and 11n (mod 6) for n={1, 2, 3, 4, 5, 6} and note that each *n* the sum n^3 + 11n = 6 (mod 6) = 0 (mod6)
For the divisibility by three we can say that since the equation n(n²+11) if n is a multiple of 3 we are set thanks to the n at the beginning and for the cases where n mod(3) is 1 or 2 we know that those squared are alwes in mod(3)=1 and that added with 11 that is mod(3)=2 is always a multiple of 3 very fascinating problem thanks for the video❤❤❤
*If n is congruent to 0 modulo 6, then n^3 + 11.n is congruent to 0^3 + 11.0 or to 0 modulo 6 *If n is congruent to 1 modulo 6, then n^3 + 11.n is congruent to 1^3 + 11.1 = 12, or to 0 modulo 6 *And so on... Another method: * If n is even then n^3 + 11.n is even (evident) If n is odd then n^3 + 11.n 1s even (odd + odd) So n^3 + 11.n is always divisible by 2 *Now we check the congruences modulo 3, it is quicker than modulo 6.. (Anyway I do like Mrcasgoldfinch's method, it is the best.)
13:35 its pretty easy to understand why tht works just think of A divides B as B/A and A divides (B+C) as (B+C)/A So, if B/A remainder = 0 {i.e. A divides B} and, if (B+C)/A = 0 {i.e. A divides (B+C)} then just split the numerator - (B+C)/A = B/A + C/A and A divides B and (B+C) therefore A divides C also for the equation to be true
If you take every part of the series n^3 +11n and devide it by 6 you'll get a curious new series where the deference between the defrences is 1,2,3,4,5... Why?
There was a slight inconsistency in the first method of proving it divides 3, you did mathematical induction only in the direction towards positive infinity, but if we want any integer, you need to show that k - 1 works too
You can also show that this is divisible by 12 for odd integers n, and for n divisible by 4. It's easiest to do when you consider the expression modulo 4, which gives you n^3 + 11*n == n^3 + 3*n == n^3 - n == n*(n^2 - 1) (mod 4). If n is divisible by 4, then the whole thing is divisible by 4. If n is odd, then n^2 == 1 (mod 4), giving the congruence n*0 == 0 (mod 4), and it's again divisible by 4. If n is even, but not divisible by 4, then n == 2 (mod 4), giving the congruence 2*(0-1) == -2 == 2 (mod 4), so it's not divisible by 4.
Regarding the proof by induction, would the current proof not be insufficient as using a base case of 1 would only prove that positive integers would make n^3 + 11n divisible by 6, not all integers? I thought you would also have to show the case P(k-1) in addition to P(k+1). So, (k-1)^3 + 11(k-1) k^3 + 11n - 3n^2 + 3n - 12 3m - 3n^2 + 3n - 12 3(m - n^2 + n - 4) And this would prove it for 0 and all negative integers.
n^3 + 11n = n(n^2 + 11) = n^3 + 2*6n - n = n(n^2 - 1) + 2*6n = n(n + 1)(n - 1) + 2*6n For 1st part of formula { n(n + 1)(n - 1) } :- ------------------------------------------------------------------- if: n = even --> (n + 1) = odd, (n - 1) = odd & n(n + 1)(n - 1) = even if: n = odd --> (n + 1) = even, (n - 1) = even & n(n + 1)(n - 1) = even So, n(n + 1)(n - 1) = even, which is divisible to 2 if: n = (2,4,6,8,10,12,..) --> (n + 1) = odd (3,5,7,9, 11,...) (n - 1) = odd (1,3,5,7,9,11,...) if: n = (1,3,5,7,9,11,..) --> (n + 1) = (2,4,6,8,10,12,...) (n - 1) = (0,2,4,6,8 ,10,...) By observation, one of n, (n + 1) or: (n - 1) equals multiple of 3. So, n(n + 1)(n - 1) equals multiple of 6. For 2nd part of formula { 2*6n } :- ----------------------------------------------------- 2*6n equals multiple of 6 So, the two parts equal multiple of 6, and the result of entire formula is divisible to 6.
For the second part (showing it is divisible by 6): The inductive proof is beautiful (although I got taught to write P(k+1)=P(k)+3*(…) to show it) I think solving with modular arithmetic is more accessible. - Let mod3(n) be the remainder of the division by 3 - If n is divisible by 3 then mod3(n) = 0 (remainder by 3 is 0) - We know (a+b)/3 = a/3 + b/3 so mod3 ( a + b ) = mod3 ( mod3(a) + mod3(b) ) - We know a*b/3 = a/3*b so mod3 (a*b) = mod3 ( mod3(a) * b) and due to symmetry mod3 (a*b) = mod3 ( mod3(a) * mod3(b) ) we need to show mod3 (n^3 + 11n) = 0 => mod3 ( (mod3 n)^3 + 11 *mod3 n) = 0 Since all n are now mod3(n) you only have to consider 0, 1, 2 0: mod3 ( 0^3 + 11*0) = 0 1: mod 3 ( 1^3 + 11*1) = mod3(12) = 0 2: mod 3 ( 2^3 + 11*2) = mod3(30) = 0
I did the 3 part a bit simpler. There are 3 possible remainders of dividing any number by 3: 0, 1, and 2. BTW, % is the modulator operator in programming, it gives you the remainder. If n % 3 = 0 (that is, n is divisible by 3), n(n^2 + 11) is divisible by 3 by definition. If n % 3 = 1 , the equation is 1^3 + 11(1) = 1 + 11 = 12. 12 % 3 = 0 If n % 3 = 2, the equation is 2^3 + 11(2) = 8 + 22 = 30. 30 % 3 = 0.
Using Euler's theorem gives a short proof when n is relatively prime to 6. n^3 + 11n = n^3 + 5n = n^3 - n = n (n^2 - 1) = n (1 - 1) = 0 (mod 6) because n^phi(6) = n^2 = 1 (mod 6) by Euler's theorem. But you also have to prove the cases where n is not relatively prime to 6. If you replace n by 2^k*m or 3^k*m in the equations above you also get 0 (mod 6).
If we check the term is divisible by 6 when n=0,1,-1 (it is), then all that has to be done is to show that when 6|n^3+11n, 6|(n+1)^3+11(n+1) and 6|(n-1)^3+11(n+1). For the first, if n^3+11n = 6z where z is some integer, consider (n+1)^3+11(n+1) (n^3+11n)+(3n^2+3n+12) 6z+3(n^2+n+4) n^2+n+4 is either a sum of two odd integers and an even integer or three even integers depending on if n is even or odd. Either way, n^2+n+4 is therefore even and so is equal to 2 times some integer y. 6z+3*2y 6(z+y) where z+y is an integer. The method is similar for n-1.
Easiest solution: We already know 3 squence number is always divisible by 6. => (n-1)n(n+1) or n(n+1)(n+2) I choose (n-1)n(n+1) because it easy to calculate. (n-1)(n+1)=n^2-1 =>(n-1)n(n+1) = n^3-n always divisible by 6. Fomula: n^3+11n = n^3-n+12n => always divisiable by 6 (12n and n^3-n always divisible by 6)
for the induction part (first half) of the video, showing that p(1) is true and that p(n+1) is true whenever p(n) is true only proves that the proposition is true for all positive integers. if you want to assert that it is true for all integers, including zero and negative integers, there is still a little more work to be done... you must also show that p(n-1) is true whenever p(n) is true.
the simplest way of showing divisibility by 6 is to show it for 2 and 3. in both the galois field with 2 and 3 elements, it simplifies down to n(n^2-1) via renaming 11 and factoring. clearly if n is 0 then the polynomial is as well. euler’s totient theorem implies that for n not 0, n^2-1 equal to (as a function and not a polynomial) 1-1 = 0.
Let’s say f(k) = k^3 + 11k is divisible by 6. (k+1)^3 + 11(k+1) = (k+1)((k+1)^2 + 11) = (k+1)(k^2 + 2k + 11 +1) = k^3 +11k + 3k^2 + 3k + 12 = (k^3 + 11k) + 3k(k+1) + 12 The first and last terms are divisible by 6, a d the middle term id divisible by 3 and 2, because either k or k+1 is even. f(1) and f(2) are divisible by 6 Therefore f(k) is divisible by 6 for all integer k.
My attempt before Watching this video - For divisibility by 6, The number must be divisible by 2 and 3 simultaneously . So,the the given integer must have a hidden multiple of 6. If we are able to identify this through the expression then it is proved My approach- n³+11n=6t =>n³+12n-n=6t =>n(n²+12)=6t+n =>n[(n+6)²-12n]=6t+n =>n(n+6)²-12n²=6t+n =>n(n+6)²=6t+n+12n² =>n(n+6)²=6t+n(12n+1) =>n(n+6)²-n(12n+1)=6t =>n[(n+6)²-(12n+1)]=6t =>n[n²+12n+36-12n-1]=6t Ughhhh I am stuck 😢
n^3+11n=n^3-n+12n. If we first prove that n^3-n is fully divisible by 6, then it is understandable that 12n is fully divisible by 6, because the number 12 is fully divisible by 6. For this, it is enough to use the method of mathematical induction and we would have that: For n=1, n^3-n=1^3-1=1-1=0, which is fully divisible by 6. For n=2, n^3-n=2^3-2=8-2=6, which is divisible by 6. For n=3, n^3-n=3^3-3=27-3=24, which is fully divisible by 6 again. We get it true for n=k, that is, k^3-k is fully divisible by 6. Let's now prove that even for n=k+1, (k+1)^3-(k+1) is fully divisible by 6 and we would have: k^3+3k^2+3k+1-k-1=(k^3-k)+3(k^2+k). We know that k^3-k is fully divisible by 6, because I got the truth from above. We see that 3(k^2+k) is also fully divisible by 6, since k^2+k is fully divisible by 2, because: k^2+k=k(k+1). We distinguish two cases for the value of k. If k is even, then it is understandable that k(k+1) is fully divisible by 2. If k is odd, then k+1 is even, so we have that k(k+1) is again fully divisible by 2. As a conclusion, the expression n^3 +11n is divisible by 6.
What makes this trick so devious is that if ‘n’ isn’t already a multiple of 3, ‘n^2’ will always result in a number 2 less than a multiple of 3 (which adding 2 and a multiple of 3 accounts for). Then the even outputs need offset which is accounted by having an odd term for the constant. To get rid of the current pattern outliers, we need them to be multiplied by 3, and since each time this occurs the input is a multiple of 3, we just multiply the entire equation by ‘n’. Now I guess I’ll watch the video…
If n is odd then n^3 and 11n both will be odd , so n^3 +11n = even or 2k , for some integer k and if we use Euclid division algorithm to n and 3 we get possible values of n= 3q , 3q+1 or 3q+2 ,for some integer q seemingly for n= 3q n^3+11n is already divisible by 3 For n= 3q+1 n^3 +11n = (3q +1)^3 +11(3q+1) = (3q+1) {9q^2+1 +6q+11}= (3q+1) (3q^2+2q+4) 3 or 3m again , for n=3q+2 n^3+11n = (3q+2) (9q^2+12q +4+11) = (3q+2)(3q^2+4q +5) 3 or 3m so, no matter what for any integer n ,n^3+11n is divisible by 3 and since GCD (2,3) =1 therefore n^3 +11n is divisible by 2×3= 6
Method 3 - n(n²+11) is divisible by 3: n=3k: 3k(9k²+11) → ok n=3k+1: (3k+1)([3k+1]²+11)=(3k+1)(9k²+6k+12)=(3k+1)×3×(3k²+2k+4) → ok n=3k+2: (3k+2)([3k+2]²+11)=(3k+1)(9k²+12k+15)=(3k+1)×3×(3k²+4k+5) → ok Conclusion: n³+11n is divisible by 3
Nice methods. A third: you can also separate the cases n≡0(mod3), n≡1(mod3), n≡2(mod3). The first case is trivial, and just putting n=k+1 or n=k+2 for some integer k that is divisible by 3 will quickly get the answer too, without knowing about induction, Fermat or spotting the n^3-n trick.
If we were to use mathematical induction, wouldn't we need to prove for the proposition P(k-1) as well, as the proof currently only shows divisibility for all integers greater than 0? Love these videos! 😀😀
We can use induction but in induction we will have to prove that n^2+n+4 is divisible by 2 which also can be done by induction If we want to use induction we have to break it into positive integers and negative integers but in this example it is enough to consider non-negative integers because of odd function
Actually, you can prove the whole proposition using induction. You end up having to prove that 3n^2+3n+12 is divisible by 6, but this is easily done via induction again. It might not be the most elegant approach, but it works.
Since 11n = 12n - n, then n^3 - 11n = n^3 - n + 12n. 12n is divisible by 6. n^3 - n = n(n^2 - 1) = (n-1) n (n+1). Three consecutive numbers are divisible by 6. Therefore, n^3 - 11n is divisible by 6.
![Prove that 11^n - 4^n is divisible by 7 for any natural number, n. [Mathematical Induction]](http://i.ytimg.com/vi/pLbG3Vvpjjk/mqdefault.jpg)
![งมหอย จับปลา มือเปล่า หาอยู่หากินแบบวีถีอีสานกับแก๊งเซียนหรั่ง ม่วนคัก! [ขอนแก่น] @Sianstudio](http://i.ytimg.com/vi/JEJZg6N-AbU/mqdefault.jpg)
I'd use this trick: n^3 + 11n = n^3 - n + 12n.
n^3 - n = n(n - 1)(n + 1) = (n - 1)*n*(n + 1). Among these three consecutive numbers n-1, n n+1, at least one is even and one is divisible by 3. Therefore their product is divisible by 2 and 3, then it's divisible by 6.
12n is also divisible by 6, so their sum (n^3 - n) + 12n = n^3 + 11n must be also divisible by 6.
I saw the video solution and it is Hella elegant. I am curious if you would try to present the problem to a middle schooler would such an approach help their understanding or just baffle them regarding how were they supposed to think it up.
I think the simplest way of looking at it would be considering the ways n can be written with regards to divisibility by 3 : n=3k or n=3k+1 or n=3k+2 with k another integer.
If n = 3k then n(n^2+11) is obviously divisible by 3 as n itself is. For the other cases we need to show n^2+11 is divisible by 3.
N=3k+1 then n^2+11=9k^2+6k+12 all members of the sum are divisible by 3 so the sum will also be
Case n=3k+2 then n^2+11= 9k^2+12k+15 which is also divisible by 3
@@dan-florinchereches4892 even easier to work in mod 3 and mod 2, so you can replace variables with 0,1,2 or 0,1 cases.
indeed the infamous math interview question about it n^3 - n, can also easily be used to show this is divisible by 12 if n is odd
Beautiful
What a beautiful ecplainatioj
If you know the Fermat's Little Theorem, we get a third method:
n^3 = n (mod 3)
then n^3 + 11n = n + 11n = 12n (mod 3)
12n = 3 * 4n = 0 (mod 3)
so we proved that the expression is divisible by 3.
Jointly with the proof of divisible by 2 explained in the video, we have that the expression is divisible by 6
Even easier. By Euler theorem: n^3=n mod 6 => n^3+11n=12n=0 mod 6.
@@Danila_Klimov But you asume that GCD(n,6)=1?
Carlos is right, you can't use Fermat's little theorem here.
I think you don’t necessarily need FLT here, just notice that the product of any three consecutive numbers is divisible by 6, thus n(n-1)(n+1)=n^3-n=0 (mod 6). Thus n^3=n (mod 6). So question= n +11n=12n=0 (mod 6).
@@ElVerdaderoAbejorro fermat little theorem in that form is always applicable, n^(p-1) = 1 mod p need (n,p) = 1, but n^p = n mod p is always true, but euler theorem does need (n,6) = 1 though
I think I found shorter proof:
Plug (n+1) instead of n:
(n+1)^3 + 11(n+1)
(n+1)((n+1)^2+11)
(n+1)(n^2+2n+12)
(n+1)(n(n+2) + 12)
n(n+1)(n+2) + 12(n+1)
Three consequtive numbers multiplied are always divisible by 6 because there must be a multiple of 2 and a multiple of 3 among them.
Very nice! Never thought of approaching this kind of (divisibility) problem this way.
@@terracottapie6872 Thanks. I actually just tried standard induction: assuming it works for n, proof for n+1. And when I got the result I realized I never used "since it works for n" part.
@@dalex641 i did the same thing!
Using modular arithmetic (thanks Gauss), all we need is to show that f(n) =: n^3 + 11n is divisible by 6 when n= 0, +-1, +-2, or 3. In fact, since f(-n) = -f(n), we need not check
n = -1 or -2.
God, I love how many equally valid ways there are to approach this. In a discipline like Math where everything is connected, it's always like a fun easter egg hunt to find all the ways you can approach a problem.
Cant we just use mathematical induction from the beginning to prove that n^3 + 11n is divisible by 6
I didn't think k of that either 😕
thats how i went about proving this
Holds for n = 0.
(n+1)^3 + 11(n+1)
= n^3 + 3n^2 + 3n + 1 + 11n + 11
= (n^3 + 11n) + 3(n^2 + n + 4)
n odd ==> n^2 odd ==> n^2 + n + 4 even
n even ==> n^2 even ==> n^2 + n + 4 even
OR n^2 + n + 4 = n(n+1) + 4 even as n(n+1) even, product of 2 consecutive integers
so last term divisible by 6, and first term is too by induction hypothesis
(And as we want to prove for all integers, we should strictly do the other direction too, that is with n -> n-1. The exact same argument will apply)
I’ve just tried to do like what you suggested when I was watching this video, and found out it is not working right away because it is impossible to show the proposition is true n=k+1 in just one step: you’ll get (k+1)^3 + 11(k+1) = 6N+ 3k^2 + 3k + 12. You can only tell by intuition that 3k^2 + 3k + 12 is only divisible by 3, but not divisible by 6
Then I have to do another M.I. to prove 3k^2 + 3k + 12 is divisible by 6 which turned out to be valid, so it proves the original proposition as well.
I have to say my method is not really efficient when compared to that in the video LOL
@@PrimeNewtonsça marche bien, on est amené à montrer que 3n²+3n+12 est divisible par 6 et donc que n²+n+4 est divisible par 2 (soit par une autte récurrence, soit par la parité)
You are an amazing guy also you have a deep passion for Mathematics.Keep going you will oneday reach 1Million subscribers.
Love from India 🇮🇳🇮🇳
Every integer kann either be written as 3k, 3k+1 or 3k+2 with k being another integer. Plug these into the formula, and every time you get an expression that is a multiple of 3.
I did the same but with 3k-1, 3k, and 3k+1. All expanded expressions are multiples of both 2 and 3.
You explain the connections so clearly that all I can say is: Respect! Also, you speak at a very good pace, so I can easily follow along even with my average English skills. I'm already looking forward to the next videos! Thank you so much, Joe.
Straightforward and tedious approach:
Let n = 6q+r, where r∈{0; 1; 2; 3; 4; 5}, then n³+11n = 216q³+108q²r+18qr²+66q+r³+11r. Everything except r³+11r is obviously divisible by 6.
0³+11·0 = 0+0 = 0
1³+11·1 = 1+11 = 12 ≡ 0 (mod 6)
2³+11·2 = 8+22 = 30 ≡ 0 (mod 6)
3³+11·3 = 27+33 = 60 ≡0 (mod 6)
4³+11·4 = 64+44 = 108 ≡ 0 (mod 6)
5³+11·5 = 125+55 = 180 ≡ 0 (mod 6).
Therefore ∀n∈ℤ, n³+11n ⋮ 6. 😉
Your method reminds me of my number theory class. We had some crazy students who did stuff like this. Nice!
In my opinion, this is the simplest and, most importantly, the most universal method. In this case, you don't even need to substitute all the numbers, because 4 = -2 and 5 = -1, and since our function is odd, it's enough to check 0, 1, and 2
@user-es6hc4qk3t it's not the simplest. If you prove it using mod 2 and mod 3 you can do the math in your head and 0 mod 2 and 0 mod 3 implies 0 mod 6 since 2 and 3 are prime factors
Slightly better method is to note that n^3+11n is even, regardless if n is even or odd. Thus, it suffices to prove that n^3+11n is a multiple of 3 and then we can do the tedious bash but with only 3 cases.
proof by calculator
my favorite
Thank you for your wonderful and blessed videos, which I enjoy very much.
Divisibility problems like this one are popular in the UK and the two most commonly used methods are proof by exhaustion and proof by induction.
When using either, a minor variation on your approach is not to consider divisibility by 2 and 3 separately but to work with 6 directly.
For proof by exhaustion:
If n is even, n=2k for some integer k and
f(n) = n^3+11n
= 8k^3+22k
= 8k(k^2-1)+30k
= 8k(k-1)(k+1)+30k
which is divisible by 6 because 6|30 and 6|k(k-1)(k+1) because three consecutive integers include at least one multiple of 2 and exactly one multiple of 3.
If n is odd, n=2k-1 for some integer k and f(n) = n^3+11n
= (8k^3+22k) - 3(2k)^2 + 3(2k) -1 - 11
= (8k^3+22k) + 6(-2k^2 + k -2)
which is divisible by 6 because 6|6 and the first term is the expression shown to be divisible by 6 in the n even case.
For proof by induction:
f(1) = 1+11=12 and 6|12
and f(k+1) = f(k) + (f(k+1)-f(k))
which is divisible by 6 because 6 | f(k) by assumption and
f(k+1) - f(k) = 3k^2 + 3k + 1 + 11
= 3k(k+1) + 12
which is divisible by 6 because 6|12 and 6| 3k(k+1) because two consecutive integers include exactly one even integer.
Like you, I prefer proof by exhaustion. And especially for this problem given that n can be non-positive. Proving divisibility by 6 for f(1) and f(k+1) proves the result only for the natural numbers. I guess this is resolved by proving the result for f(k-1) similarly - this is fine as f(k-1)-f(k) = -3k(k-1) - 12 which is divisible by 6 for the same reasons as given above - so that the dominoes then fall in both directions from f(1) simultaneously. The need for this is avoided by using exhaustion, where the integer k is unrestricted.
Again, thank you for your lovely videos and i look forward to seeing the next one. God bless yuu ❤
My teacher in India told us of another method: Proof by intimidation 😅
I could do it in 2 ways:
1. using modular artihmetics, simply show that for n = 1, 2, 3, 4, or 5 this results in a multiple of 6.
2. n^3 + 11n = n^3 -n + 12n.
12n is a multiple of 12 which is a multiple of 6.
and n^3 - n is a product of 3 consecutive numbers: (n-1)n(n+1)
so there's gotta be an even number and a multiple of 3 in it.
Both of them will take LESS than 16 minutes
Never Stop Teaching!
Prove that for any integer n. n^3+11n is divisible by 6. To show that n^3+11n is divisible by 6, we need to show that n^3+11n is n is even and it’s a multiple of 3.
Love your channel ... you combine elegant problem solving skills with a very soothing teaching style. That said, I have to admit that I am bit passed high school ... 68 years young to be exact. All-in-all ... brain food (for geeks!) ...
(n-1)n(n+1)+12n
Nice
But, how will he make a big video if you find such a simple proof?
Your mathematical induction does not complete the proof. It only shows that 3 divides n³+11n if n is a natural number. You could say that if n is negative then n=-j for j is a natural number, and then show that (-j)³+11(-j)=-(j³+11j), and then using your M.I this is also divisible by 3. You would also need to test n=0 to complete the set of integers.
You can also just do the induction step the opposite way. IE if you show that when it's true for k that it's also true for k-1 the same way that you show that it's true for k+1. No need for specifically testing just negative numbers or testing 0 individually, any base case is sufficient to prove it for all integers.
@@phiefer3 That's true
0+0 = 0 is trivial
Mathematical induction shows that if it's true for n then it's true for n+1. It's obviously true for 0, therefore it's true for all non-negative integers. And it's likewise obviously true for all integers, since negative integers are just positive integers * -1, and if you multiply a number that's divisible by 3 by an integer (like -1) then the result is also divisible by three.
@@ptorq yeah but you still gotta show it as part of the proof
n^3+11n is divisible by 6 proof by modular arithmetic.
Write n as the largest multiple of 6 plus its residu i.e. n = 6a + b where b is an integer between 0 and 5
now work out n^3 + 11n = (6a+b)^3 + 11(6a+b)
=> (6a)^3 + 3b * (6a)^2 + 3 * 6a * b^2 + b^3 + 11 * 6a + 11b
group all the factors with an a in it.
⇒ 6a^3 + 6 * 3ba^2 + 6 * 3 ab^2 + 6 * 11a + b^3 +11b
every factor with an a in it, has a factor of 6 associated with it. therefor these factors are always divisible by 6 and can be ignored for the rest of the proof.
The remaining factors are: b^3 + 11b. Which is in the same form as our starting question but b is limited in its range to the integers from 0 to 5. These can be easily checked by hand.
first rewrite b^3 + 11b to b(b^2+11).
for this equation to be divisible by 6 one of the factors needs to be divisible by 6 or one is divisible by 2 and the other is divisible by 3
b | b^2 +11
0 | 11 0 is divisible by 6 ✓
1 | 12 12 is divisible by 6 ✓
2 | 15 2 is divisible by 2 and 15 is divisible by 3✓
3 | 20 20 is divisible by 2 and 3 is divisible by 3✓
4 | 27 4 is divisible by 2 and 27 is divisible by 3✓
5 | 36 36 is divisible by 6 ✓
All 6 cases work out. this means that the starting equation is divisible by 6
QED
It is a nice starting problem to get into modular arithmetic in my opinion.
I like this guy. The way he's passionate about maths shows in the content he makes :)
I love your videos ! It brings me back to my professors in the eighties.
Proof using Product of N consecutive integers is divisible by N! (This theorem is also be proved below)
Consider product of 3 consecutive integers : (n-1) * (n) * (n+1). This is divisible by 3!, that is by 6, by the above theorem -- (1)
(n-1) * (n) * (n+1) = n(n^2-1) = n^3 - n
Adding & Subtracting 12n
n^3 - n = n^3 - n + 12n - 12n = n^3 + 11n - 12n
From (1) n^3 + 11n - 12n is divisible by 6
Since 12n is divisible by 6, it follows that n^3 + 11n should also be divisible by 6
Q.E.D
=======================================================================================================
Proof of Product of N consecutive integers is divisible by N!
Given the product of 'n' consecutive integers [m-(n-1)]*[m-(n-2)]*[m-(n-3)]...[m-2]*[m-1]*m, prove it is divisible by n!
n! = n*(n-1)*(n-2)*(n-3)....3*2*1
Consider the divisibility of [m-(n-1)] term from above product by n
Either n divides [m-(n-1)] or it doesn't and leaves a remainder r. If it divides, then there is nothing to prove. If it doesn't, we can write express :
[m-(n-1)] = n*k + r. Here 0 < r < n
This implies [m-(n-1)] would be divisible by n, if r were to be added to it
Notice that the given product has (n-1) consecutive terms excluding [m-(n-1)].
Therefore, by successively incrementing [m-(n-1)] by 1, one of the successive terms in the product would be divisible by n, as the remainder r
1) If n is even
n^3 + 11 n =n(n^2+11) is even.
2)if n is odd
n^2 is odd [square of odd (odd*odd) is odd]
n^2 +11= odd + odd =even
n(n^2 +11)= odd *even =even
Hence if n is even /odd,
n^3 + 11n is even. Hence it is divisible by 2 **
Now
3)
If n is a multiple of 3
n^3+11n=n(n^ 2+11) is a multiple of 3
4)if n is not a multiple of 3, then n will leave 1/2 as remainder when it is divided by 3
Hence in this case
I) n= 3 k +1 OR ii) n = 3k +2
I) If n =3k +1
n^2+11
=9k^2 +6k +12
=3(3k^2+ 2k +4)
is divisible by 3
Hence n^3+11n
= n(n^2+11)
> n* a number divisible by 3
Hence n^3+11n is divisible by 3 when n is not divisible
3 and leave remainder 1 when n is divided by 3.
ii)
If n=3k +2
then n^2+11
=9k^2 +12k +15
=3(3k^2+4k+ 5)
Hence n^ 2 +11 is divisible by 3
Hence n^3 +11n
=n (n^2+11)
> n* a number divisible by 3
Hence n^3+11n is divisible by 3 when n is not divisible by 3 and leave remainder 2 when it is divided by 3
Hence n^3+11n is divisible by 3 if n is not divisible by 3
Hence it is proved that n^3+11n is divisible by 2 & 3 and so it is divisible by 2*3 ie 6
Comment please
i like it, but i would use a slightly different approach.
first i'd get, that n^3+11n = even (same as everybody does).
then, let's look if we can extract 3 somehow.
as we see - n is cubed. so, n*(n+1)(n+2) definately gives us divisibility with 3 and cube, what does it lack?
>> n(n+1)(n+2) = n (n^2 + 3n +2) = n^3 + 3n^2 + 2n
okay, then, let's substract what we had in the beginning, and look of "extra parts":
>> n^3 + 3n^2 + 2n - n^3 -11n = 3n^2 - 9n
love the way you explain things slowly and clearly
Beautiful solution!
A fantastic demonstration of mathematical induction, in particular.
Thank you!
I found an odd way of proving it:
The difference between consecutive whole number cubes is a Σ(6•(0-n))+1, and the difference between consecutive multiples of 11 is, well, 11
Since the equation is a sum I can borrow the +1 from the cube side and tack it onto the 11x side, making the difference between each consecutive solution Σ(6·(0-n))+12
And that is divisible by 6 for every whole number n
I'm nearing 50, but have always been interested in high school math. This caught my attention and I actually watched the whole video. Thanks for posting. Cheers from India.
Lots of alternative proofs in the comments, one I didn’t see is simply “brute forcing” to see the formula is always equal to zero mod 2 and mod 3.
Mod 2: Test 0 and 1
0 ³ + 11*0 = 0 mod 2
1 ³ + 11*1 = 12 = 0 mod 2
Mod 3: test -1, 0, and 1
-1 ³ + 11*(-1) = -12 = 0 mod 3
0 ³ + 11*0 = 0 mod 3
1 ³ + 11*1 = 12 = 0 mod 3
So since all possible cases mod 2 and mod 3 equal 0 in those modulos, the formula is also always 0 mod 6.
I didn't think of that.
I'm surprised modular arithmetic wasn't one of the suggested proofs to show that the equation is divisible by 3
n % 3 must be in the set {0, 1, 2}, therefore, if all of these equal 0 when plugged into the equation modulo 3, every value of n is.
Case 1: n % 3 = 0
(n^3 + 11n) % 3 = 0*0*0 + 2 * 0 = 0
Case 2: n % 3 = 1
(n^3 + 11n) % 3 = 1*1*1 + 2 * 1 = 1 + 2 = 0
Case 3: n % 3 = 2
(n^3 + 11n) % 3 = 2*2*2 + 2 * 2 = 2 + 1 = 0
Therefore, n^3 + 11n is divisible by 3
Even shorter: n³ + 11n = n (n² + 11) = n(n² - 1) = (n-1)n(n+1) (mod 6)
And you're done
Excellent presentation! (And you have the cleanest blackboards I've ever seen!)
I never understood people that say: “Math is boring.”, it’s beautiful! I wish I had you as my math teacher in my school days.
For cleaner induction proof, instead of a new variable, you can use mod 3 = 0 notation.
I used induction, checking f(1) and then setting f(k) = 6m, and then f(k+1) = 6m + 3k^2 + 3k + 12. This is divisible by three, so you get f(k+1)/3 = 2m+k^2 + k + 4. Set g(n) = n^2+n+4, and prove this is divisible by two by induction. Check g(1), then continue with g(k) = 2t, g(k+1) = 2t + 2k + 2. This is divisible by two, so you get g(k)/2 = t+k+1. Put this back into the original function, and you get f(k+1)/3 = 2m+2t+2k+2. Therefore f(k+1)/6 = m+t+k+1, so f(n) is divisible by 6.
For the divisible by 3 one, I used a different approach, which uses modular arithmetic.
So for any integer n in n mod 3 , there will be 3 results, which are 0, 1, and 2
For result 0, substituting it to the original equation gives 0, which is a multiple of 3.
For result 1, substituting it gives 12, which is a multiple of 3.
And for result 2, substituting it gives 30, which again, is a multiple of 3.
Hope this helps :)
n^3+11n = (n^3-n)+12n= n*(n^2-1)+6*(2n) = (n-1)*n*(n+1) + 6*2n
The product of three consecutive integers is always divisible by 6, because exactly one of those three is a multiple of three (the other two are 3 mod 1 and 3 mod 2), and either n is even or both n-1 and n+1 are even, so the product is a multiple of 2. Thus, the whole thing is divisible by 6.
You can use induction directly to prove for 6
6m + 3k^2 + 3k +12 = 6m + 3(k^2 + k + 4)
Number in brackets is always even so
6m + 3(2n) = 6m + 3*2(n) = 6( m + n)
Method 3:
Same argument for divisible by 2.
For divisible by 3:
There are 3 cases:
n mod 3 = 0
n mod 3 = 1
n mod 3 = 2
For n mod 3 = 0:
n is divisible by 3, so n(n^2+11) must be too because it has n as a factor.
If n mod 3 = 1 or 2, the expression can only be divisible by 3 if n^2+11 is, because the factor n will not have prime factor 3.
If n mod 3 = 1, n can be written as 3k-1, with k being an integer as per definition of the modulo operation.
(3k-1)^2+11 = 9k^2-6k+1+11 = 3(3k^2 - 2k + 4) which has factor 3 and thus is divisible by 3
If n mod 3 = 2, n = 3k-2, with k an integer.
(3k-2)^2+11 = 9k^2-12k+4+11 = 3(3k^2 - 4k + 5) which has factor 3.
I hope my bad English won't lead to confusion, but what I love most about your videos is the beauty of your writing,
Your "Method 2" delves into the theory of Congruences. After a few frustrating failures at solving the problem, I thought I might have to do the same. So I reviewed Congruences in Courant & Robbins and decided it could be done that way - thanks for the demo!
But then it struck me that the induction approach might be just as easy, so I tried that instead. I got pretty well as far as you did with P(k) and P(k+1) (except that I kept using 'n'). I then realized that if I worked out what has to be added to P(n) to get P(n+1), and could prove that the added bit evaluates to a multiple of 6, I'd have the proof (since P(1), which is 12, is a multiple of 6).
So I went:
P(n) = n^3 + 11n
P(n+1) = n^3 + 3n^2 + 3n + 1 + 11n + 11.
By inspection, the added bit is 3n^2 + 3n + 12, which I wrote as 3n(n + 1) + 12. This is a multiple of 3, but also a multiple of 2 - because n(n+1) is an odd number times an even number, and the '12' at the end is also a multiple of 3x2. Done - QED.
In summary, I more or less duplicated your "Method 1", but I demonstrated divisibility by both 3 and 2 in the same line.
Quite a neat little problem - I might include it in the book I'm currently writing (any idea who should be acknowledged ?).
As someone who loves math but really sucks with thought process skills, its a great way to learn thank you so much sir from India.
Guys, you might be using shortcuts but he is just doing it the most logical way. Well explained, appreciated
Proving divisibility by 3 is simpler if you stick to the same factored form as you used in the 'even' proof. 3 cases: case 1: n is multiple of 3, so can be represented as 3k. So you have (3)(k)(9k² + 11). Is (3)(integer) so divisible by 3. Case 2: n = 3K + 1. Then we have (3k + 1)[(3k + 1)² + 11] which simplifies to
(3k + 1)(3)(3k² + 2k + 4). We have (integer)(3)(integer) so divisible by 3. Case 3: n = 3k - 1. Then is
(3k - 1)(3)(3k² - 2k + 4) which is also (integer)(3)(integer) so divisible by 3.
This second method was so elegant!!!
I didn't see where this was going until you expanded n²-1 to (n-1)(n+1) and when I saw the product of three consecutive numbers, this put a big smile on face. Beautiful!
I found the way you used the induction a little strange. Maybe it's the way I was taught.
The way I'd do it would be like this:
First step is like yours: show that the proposition is true for f(1): 1³+11×1 = 12; 12 is divisible by 3. Actually, we could even have started with f(0): 0³ + 11×0 = 0; 0 is divisible by 3, albeit it looks almost too simple! 😅
The second step is where I took a slightly different approach. I started with the difference f(k+1)-f(k).
f(k+1)-f(k) =
[(k+1)³ + 11(k+1)] - [k³ + 11k] =
[(k³+3k²+3k+1) + 11k+11] - [k³ + 11k] = [here we can cancel k³ and 11k]
3k²+3k+1 + 11 =
3k² + 3k + 12 =
3 (k²+k+4)
What we have shown in this second step is that the difference between the value of the function of two consecutive numbers is divisible by 3. The difference to your approach is that I am not assuming, as you've done at 6:38, that f(k) is divisible by 3. I think, if we want to be rigorous, you'd have to be more explicit to show that your assumption was valid. I thought your approach through and see how one can make that case (the algebra of the two approaches is very similar after all) but I would have liked this to be more explicit.
Anyway, like I said, we have shown that the difference between the value of f(n) and f(n+1) is divisible by 3, which means that if f(n) is divisible by 3 (which remains to be shown), then f(n+1) will also be divisible by 3. I realize now that I used that theorem from your method 2. 😉
Now step 1 comes into the picture. We know that f(1) is divisible by 3, therefore applying step 2 f(2) is as well. As, since we used mathematical induction, are f(3), f(4), f(5)... all the way up to infinity.
It should be noted that technically we aren't finished yet because we only have shown that n³+11n is divisible by 3 for all n≥1 but not n
Beautiful work! I look forward to seeing more. I was hoping to see you work with the modulus rules. They're currently mystifying me.
Induction also works without dividing 6 into its factors. n=1 gives 12. Them set k^3+11k = 6m.
k -> k+1 gives 6m+3(k^2+k+4)
k^2+k+4 is always even, so call it 2p.
Then we have 6(m+p), which is always divisible by 6.
I didn't see Method 2 coming. Thanks for explaining it--very cool. I had better never stop learning!
I really like your video and you happiness in solving math problem ❤
very clean writing, is this using hagoromo chalk?
My proof before watching:
Let S = n^3 + 11n = n(n^2 + 11)
If n is even, then S is even.
If n is odd, then n^2 + 11 is an odd number plus an odd number, which is even. So S is even.
n must be even or odd, and in both cases S is even.
If n is divisible by 3, then S is divisible by 3.
If n is not divisible by 3, then n = 3k + 1 or n = 3k + 2 where k is an integer.
If n = 3k + 1, then S = (3k + 1)((3k + 1)^2 + 11) = (3k + 1)(9k^2 + 6k + 12) = 3(3k + 1)(3k^2 + 2k + 4), which is divisible by 3.
If n = 3k + 2, then S = (3k + 2)((3k + 2)^2 + 11) = (3k + 2)(9k^2 + 12k + 15) = 3(3k + 2)(3k^2 + 4k + 5), which is divisible by 3.
n must be either divisible by 3 or not divisible by 3, and in both cases S is divisible by 3.
Since S is both divisible by 2 and divisible by 3, it is divisible by 2 * 3 = 6.
Incredible ! This is exactly, but exactly the solution I thought of too !
Here's my very short proof:
In Z/6Z (and all the more in Z/2Z and Z/3Z) we have: n^3 + 11n = n^3 - n = n.(n-1).(n+1)
The latter product is 0 in both Z/2Z and Z/3Z since (at least) one of its factors is always 0, no matter what n is.
So we know that both 2 and 3 divide n^3 + 11n, and, since 2 and 3 are relative prime (their gcd is 1), 6 must also divide it. q.e.d.
Before watching this video, here's my solution:
Base case: n = 0, 0^3+11(0)=0 which is is divisible by 6
Claim: n^3 + 11n is divisible by 6
Proof by induction:
(n+1)^3 + 11(n+1)
= n^3 + 3n^2 + 3n + 1 + 11n + 11
= n^3 + 3n^2 + 14n + 12
if k + 12 is divisible by 6, k is divisible by 6, therefore we can get rid of the + 12 term
-> n^3 + 3n^2 + 14n
Since we assume n^3 + 11n is divisible by 6 we can use the same logic and subtract n^3 + 11n
-> 3n^2 + 3n
= 3n(n+1)
n(n+1) is always even since either n or n+1 must be even, thus we can rewrite n(n+1) as 2*a, where a is an integer
thus 3n(n+1) = 3*2*a = 6*a
QED
Hopefully this is valid :)
Product of k consecutive integers is divisible by k!, so (n³-n) is divisible by 6 and 12n is divisible by 6...hence (n³+11n) is divisible by 6... Amazing method and work sir!!
I really like the second method, because it is very elegant and short.
Your induction proof however is incomplete because with starting at 1 and the induction step n+1 you have shown this only for positive integer but not for all integer.
I approached it a little different. It's more straight forward but also longer. The beginning is the same, so I also proved that n^3+11n is even.
Then you can make 3 cases for n: it can be congruent to 0, 1 or 2 mod 3.
case 1: 0 => we can write n as n=3k with k being an integer. Therefor n^3+11n=(3k)^3+11*3k=27k^3+33k=3(9k+11k). Therefor the divisibility by 3 is shown for this case as 3 is a factor.
case 2: 1 => we can write n as 3k+1 with k being an integer. Therefor we get
(3k+1)^3+11(3k+1)=27k^3+27K^2+9k+1+33k+11=3(9k^3+9k^2+14k+4), again 3 is factor and the divisibility by 3 is shown.
case 3: 2 => we can write n as 3k+2 with k being an integer. Therefor we get
(3k+2)^3+11(3k+2)=27k^3+54k^2+36k+8+33k+22=3(9k^3+18k^2+23k+10) and again 3 is a factor and the divisibility is also shown for this case
I loved this proof! I saw this on my recommended, and I thought: "No way you can prove something like that! Not even any constants to base it upon!" In all honesty, I like the number theory method of proving it better (even though I didn't even know any until now 😁). It turns out I was overthinking the entire way of solving it, I find it intriguing that it was solved mainly using logic, rather than you know, numbers, etc... 😃😃😃
Another method is to calculate the difference between two consecutive terms of the series n^3 + 11n, since (n+1)^3 + 11(n+1) - n^3 - 11n = 3(n^2 + n + 12), we are trying to show that the difference between two terms is a multiple of 6 (and thus prove by induction that all terms are divisible by 6), 6 can be factored into 3 and 2, there is already a 3 in the equation. So the problem is reduced to showing that n^2 + n + 11 is even for all integers n. You can consider the cases when n is even and when n is odd separately to show this. The base case is (1)^3 + 11(1) = 12 which is divisible by 6, so all terms are divisible by 6
The second method was really interesting, as my approach to solve this problem would always be mathematical induction from the beginning. Enjoyed it!
This was a good refresher for me on using induction , and the second method requires a lot more phantasy... thanks!
n³(mod 6) ≡ n. (I didn't know this, but it takes 20 seconds to check the possibilities.) 11(mod 6) ≡ -1. So [n³ - 11n](mod 6) ≡ n - n = 0. QED.
You are a master of patient, crystal-clear descriptions of ludicrously complicated approaches.
You don’t need to check the possibilities. Phi(6) = (2-1)(3-1) = 2. So n^2 = 1 mod 6, and so n^3 = n mod 6.
In general, x^phi(m) = 1 mod m so long as x != 0 mod m. (Look up “Euler’s totient function” in Wikipedia)
So you have two cases:
* n = 0 mod 6, in which case n^3 + 11n = 0 mod 6, trivially
* n != 0 mod 6, in which case n^3 + 11n = n^(phi(6) + 1) + (12-1)n = n - n = 0 mod 6.
To see the divisibility by 3, I just consider the following cases:
a) n = 0 (mod 3) --> n^3 + 11n = 0 + 0 = 0 (mod 3)
b) n = 1 (mod 3) --> n^3 + 11n = 1 + 11 = 12 = 0 (mod 3)
c) n = 2 (mod 3) --> n^3 + 11n = 8 + 22 = 30 = 0 (mod 3)
This shows that n^3 + 11n is divisible by 3.
Un bel exposé, clair et précis, et une méthode bien choisie. Beau travail. 👍👍
Il existe une solution beaucoup PLUS COURTE (une ligne) que je te propose pour le plaisir.
n³+11n = n³ - n + 12n
donc 6 divise n³+11n 6 divise n³ - n car 12n est un multiple de 6.
Or n³-n = n(n²-1) = (n-1)n(n+1). Produit de 3 nombres consecutifs.
donc divisible par 2 et par 3 qui sont premiers entr'eux, donc ce produit est divisible par leur produit qui est 6.😉😉
Si on souhaite faire une démonstration par récurrence, on peut faire directement une récurrence en supposant P(n) divisible par 6. Elle ressemble beaucoup à ce que tu as écrit.
You just defied my expectations. Well done.
Hey, man! I like how you always say "Never stop learning."
The simplest proof without much thought: Check for n = 0 to 5 whether mod(n^3 + 11*n, 6) = 0. Bingo.
Hi, in your 2nd proof I would find more natural to start with B=(n-1)*n*(n+1) since it's obviously multiple of 3; then choose C=(+ or -)(n^3+11*n) since it can be divisible by 3 regardless of the sign; then compute B+C with both signs and see whether at least one of the sums is multiple of 3 (in this case, choosing "-" yields B+C=-12*n.)
A very simple approach: Since 6 is kind of small number, just build a table of n^3 (mod 6) and 11n (mod 6) for n={1, 2, 3, 4, 5, 6} and
note that each *n* the sum n^3 + 11n = 6 (mod 6) = 0 (mod6)
For the divisibility by three we can say that since the equation n(n²+11) if n is a multiple of 3 we are set thanks to the n at the beginning and for the cases where n mod(3) is 1 or 2 we know that those squared are alwes in mod(3)=1 and that added with 11 that is mod(3)=2 is always a multiple of 3 very fascinating problem thanks for the video❤❤❤
It's trivial. It suffices to check the cases where 0
*If n is congruent to 0 modulo 6, then n^3 + 11.n is congruent to 0^3 + 11.0 or to 0 modulo 6
*If n is congruent to 1 modulo 6, then n^3 + 11.n is congruent to 1^3 + 11.1 = 12, or to 0 modulo 6
*And so on...
Another method:
* If n is even then n^3 + 11.n is even (evident)
If n is odd then n^3 + 11.n 1s even (odd + odd)
So n^3 + 11.n is always divisible by 2
*Now we check the congruences modulo 3, it is quicker than modulo 6..
(Anyway I do like Mrcasgoldfinch's method, it is the best.)
Anche io ho pensato così
13:35 its pretty easy to understand why tht works
just think of A divides B as B/A and
A divides (B+C) as (B+C)/A
So, if B/A remainder = 0 {i.e. A divides B}
and, if (B+C)/A = 0 {i.e. A divides (B+C)}
then just split the numerator - (B+C)/A = B/A + C/A
and A divides B and (B+C)
therefore A divides C also for the equation to be true
If you take every part of the series n^3 +11n and devide it by 6 you'll get a curious new series where the deference between the defrences is 1,2,3,4,5...
Why?
There was a slight inconsistency in the first method of proving it divides 3, you did mathematical induction only in the direction towards positive infinity, but if we want any integer, you need to show that k - 1 works too
Yeah, I was wondering about that, it seems the induction only proved it for positive n.
n^3+11n=n(n^2=11), then you could go through cases if you take n modulo 6 (0, ±1, ±2, ±3).
Nice problem and great solution, just please, light a little bit more the studio.very dark, no lights.
Thank you for good video👍
You can also show that this is divisible by 12 for odd integers n, and for n divisible by 4. It's easiest to do when you consider the expression modulo 4, which gives you n^3 + 11*n == n^3 + 3*n == n^3 - n == n*(n^2 - 1) (mod 4). If n is divisible by 4, then the whole thing is divisible by 4. If n is odd, then n^2 == 1 (mod 4), giving the congruence n*0 == 0 (mod 4), and it's again divisible by 4. If n is even, but not divisible by 4, then n == 2 (mod 4), giving the congruence 2*(0-1) == -2 == 2 (mod 4), so it's not divisible by 4.
Mathematical induction such a beautiful amd powerful tool
Regarding the proof by induction, would the current proof not be insufficient as using a base case of 1 would only prove that positive integers would make n^3 + 11n divisible by 6, not all integers?
I thought you would also have to show the case P(k-1) in addition to P(k+1).
So, (k-1)^3 + 11(k-1)
k^3 + 11n - 3n^2 + 3n - 12
3m - 3n^2 + 3n - 12
3(m - n^2 + n - 4)
And this would prove it for 0 and all negative integers.
Or use the fact that f is an odd function to show f(-n)=-f(n)
n^3 + 11n
= n(n^2 + 11)
= n^3 + 2*6n - n
= n(n^2 - 1) + 2*6n
= n(n + 1)(n - 1) + 2*6n
For 1st part of formula { n(n + 1)(n - 1) } :-
-------------------------------------------------------------------
if: n = even --> (n + 1) = odd, (n - 1) = odd & n(n + 1)(n - 1) = even
if: n = odd --> (n + 1) = even, (n - 1) = even & n(n + 1)(n - 1) = even
So, n(n + 1)(n - 1) = even, which is divisible to 2
if: n = (2,4,6,8,10,12,..) --> (n + 1) = odd (3,5,7,9, 11,...)
(n - 1) = odd (1,3,5,7,9,11,...)
if: n = (1,3,5,7,9,11,..) --> (n + 1) = (2,4,6,8,10,12,...)
(n - 1) = (0,2,4,6,8 ,10,...)
By observation,
one of n, (n + 1) or: (n - 1) equals multiple of 3.
So, n(n + 1)(n - 1) equals multiple of 6.
For 2nd part of formula { 2*6n } :-
-----------------------------------------------------
2*6n equals multiple of 6
So, the two parts equal multiple of 6, and the result of entire formula is divisible to 6.
For the second part (showing it is divisible by 6): The inductive proof is beautiful (although I got taught to write P(k+1)=P(k)+3*(…) to show it) I think solving with modular arithmetic is more accessible.
- Let mod3(n) be the remainder of the division by 3
- If n is divisible by 3 then mod3(n) = 0 (remainder by 3 is 0)
- We know (a+b)/3 = a/3 + b/3 so mod3 ( a + b ) = mod3 ( mod3(a) + mod3(b) )
- We know a*b/3 = a/3*b so mod3 (a*b) = mod3 ( mod3(a) * b) and due to symmetry mod3 (a*b) = mod3 ( mod3(a) * mod3(b) )
we need to show mod3 (n^3 + 11n) = 0
=> mod3 ( (mod3 n)^3 + 11 *mod3 n) = 0
Since all n are now mod3(n) you only have to consider 0, 1, 2
0: mod3 ( 0^3 + 11*0) = 0
1: mod 3 ( 1^3 + 11*1) = mod3(12) = 0
2: mod 3 ( 2^3 + 11*2) = mod3(30) = 0
I did the 3 part a bit simpler.
There are 3 possible remainders of dividing any number by 3: 0, 1, and 2.
BTW, % is the modulator operator in programming, it gives you the remainder.
If n % 3 = 0 (that is, n is divisible by 3), n(n^2 + 11) is divisible by 3 by definition.
If n % 3 = 1 , the equation is 1^3 + 11(1) = 1 + 11 = 12. 12 % 3 = 0
If n % 3 = 2, the equation is 2^3 + 11(2) = 8 + 22 = 30. 30 % 3 = 0.
Elegant presentation! Thanks for posting.
Using Euler's theorem gives a short proof when n is relatively prime to 6.
n^3 + 11n = n^3 + 5n = n^3 - n = n (n^2 - 1) = n (1 - 1) = 0 (mod 6)
because n^phi(6) = n^2 = 1 (mod 6) by Euler's theorem. But you also have to prove the cases where n is not relatively prime to 6. If you replace n by 2^k*m or 3^k*m in the equations above you also get 0 (mod 6).
If we check the term is divisible by 6 when n=0,1,-1 (it is), then all that has to be done is to show that when 6|n^3+11n, 6|(n+1)^3+11(n+1) and 6|(n-1)^3+11(n+1). For the first, if n^3+11n = 6z where z is some integer, consider
(n+1)^3+11(n+1)
(n^3+11n)+(3n^2+3n+12)
6z+3(n^2+n+4)
n^2+n+4 is either a sum of two odd integers and an even integer or three even integers depending on if n is even or odd. Either way, n^2+n+4 is therefore even and so is equal to 2 times some integer y.
6z+3*2y
6(z+y) where z+y is an integer.
The method is similar for n-1.
Easiest solution:
We already know 3 squence number is always divisible by 6.
=> (n-1)n(n+1) or n(n+1)(n+2)
I choose (n-1)n(n+1) because it easy to calculate. (n-1)(n+1)=n^2-1
=>(n-1)n(n+1) = n^3-n always divisible by 6.
Fomula: n^3+11n
= n^3-n+12n => always divisiable by 6 (12n and n^3-n always divisible by 6)
for the induction part (first half) of the video, showing that p(1) is true and that p(n+1) is true whenever p(n) is true only proves that the proposition is true for all positive integers. if you want to assert that it is true for all integers, including zero and negative integers, there is still a little more work to be done... you must also show that p(n-1) is true whenever p(n) is true.
the simplest way of showing divisibility by 6 is to show it for 2 and 3. in both the galois field with 2 and 3 elements, it simplifies down to n(n^2-1) via renaming 11 and factoring. clearly if n is 0 then the polynomial is as well. euler’s totient theorem implies that for n not 0, n^2-1 equal to (as a function and not a polynomial) 1-1 = 0.
Let’s say f(k) = k^3 + 11k is divisible by 6.
(k+1)^3 + 11(k+1)
= (k+1)((k+1)^2 + 11)
= (k+1)(k^2 + 2k + 11 +1)
= k^3 +11k + 3k^2 + 3k + 12
= (k^3 + 11k) + 3k(k+1) + 12
The first and last terms are divisible by 6, a d the middle term id divisible by 3 and 2, because either k or k+1 is even.
f(1) and f(2) are divisible by 6
Therefore f(k) is divisible by 6 for all integer k.
My attempt before Watching this video -
For divisibility by 6,
The number must be divisible by 2 and 3 simultaneously .
So,the the given integer must have a hidden multiple of 6. If we are able to identify this through the expression then it is proved
My approach-
n³+11n=6t
=>n³+12n-n=6t
=>n(n²+12)=6t+n
=>n[(n+6)²-12n]=6t+n
=>n(n+6)²-12n²=6t+n
=>n(n+6)²=6t+n+12n²
=>n(n+6)²=6t+n(12n+1)
=>n(n+6)²-n(12n+1)=6t
=>n[(n+6)²-(12n+1)]=6t
=>n[n²+12n+36-12n-1]=6t
Ughhhh I am stuck 😢
Bro your channel is awesome man keep up the good work man
n^3+11n=n^3-n+12n. If we first prove that n^3-n is fully divisible by 6, then it is understandable that 12n is fully divisible by 6, because the number 12 is fully divisible by 6. For this, it is enough to use the method of mathematical induction and we would have that: For n=1, n^3-n=1^3-1=1-1=0, which is fully divisible by 6. For n=2, n^3-n=2^3-2=8-2=6, which is divisible by 6. For n=3, n^3-n=3^3-3=27-3=24, which is fully divisible by 6 again. We get it true for n=k, that is, k^3-k is fully divisible by 6. Let's now prove that even for n=k+1, (k+1)^3-(k+1) is fully divisible by 6 and we would have: k^3+3k^2+3k+1-k-1=(k^3-k)+3(k^2+k). We know that k^3-k is fully divisible by 6, because I got the truth from above. We see that 3(k^2+k) is also fully divisible by 6, since k^2+k is fully divisible by 2, because: k^2+k=k(k+1). We distinguish two cases for the value of k. If k is even, then it is understandable that k(k+1) is fully divisible by 2. If k is odd, then k+1 is even, so we have that k(k+1) is again fully divisible by 2. As a conclusion, the expression n^3 +11n is divisible by 6.
I used modular arithmetic (mod 6).
True for 0, 1^3+11=12, 2^3+22=30, 3^3+33=60, notice also that 4=-2, 5=-1 modulo 6.
This. Whole problem takes about 15 seconds to do in your head.
What makes this trick so devious is that if ‘n’ isn’t already a multiple of 3, ‘n^2’ will always result in a number 2 less than a multiple of 3 (which adding 2 and a multiple of 3 accounts for).
Then the even outputs need offset which is accounted by having an odd term for the constant.
To get rid of the current pattern outliers, we need them to be multiplied by 3, and since each time this occurs the input is a multiple of 3, we just multiply the entire equation by ‘n’.
Now I guess I’ll watch the video…
If n is odd then n^3 and 11n both will be odd , so n^3 +11n = even or 2k , for some integer k
and if we use Euclid division algorithm to n and 3 we get possible values of n= 3q , 3q+1 or 3q+2 ,for some integer q
seemingly for n= 3q n^3+11n is already divisible by 3
For n= 3q+1
n^3 +11n = (3q +1)^3 +11(3q+1) = (3q+1) {9q^2+1 +6q+11}= (3q+1) (3q^2+2q+4) 3 or 3m
again , for n=3q+2
n^3+11n = (3q+2) (9q^2+12q +4+11) = (3q+2)(3q^2+4q +5) 3 or 3m
so, no matter what for any integer n ,n^3+11n is divisible by 3 and since GCD (2,3) =1 therefore n^3 +11n is divisible by 2×3= 6
We can also let n^3 + 11n = either 3m , 3m+1 , or 3m+2
Then put in the value of n in the eq. We will get a "multiple of 3" equations easily
Method 3 - n(n²+11) is divisible by 3:
n=3k: 3k(9k²+11) → ok
n=3k+1: (3k+1)([3k+1]²+11)=(3k+1)(9k²+6k+12)=(3k+1)×3×(3k²+2k+4) → ok
n=3k+2: (3k+2)([3k+2]²+11)=(3k+1)(9k²+12k+15)=(3k+1)×3×(3k²+4k+5) → ok
Conclusion: n³+11n is divisible by 3
I think modular arithmetic is the fastest way but it’s lovely to see other methods used!
Second method is genius in its simplicity. And it is the total solution as it includes both 2 and 3 as factors as pinned already.
Nice methods. A third: you can also separate the cases n≡0(mod3), n≡1(mod3), n≡2(mod3). The first case is trivial, and just putting n=k+1 or n=k+2 for some integer k that is divisible by 3 will quickly get the answer too, without knowing about induction, Fermat or spotting the n^3-n trick.
If we were to use mathematical induction, wouldn't we need to prove for the proposition P(k-1) as well, as the proof currently only shows divisibility for all integers greater than 0?
Love these videos! 😀😀
We can use induction but in induction we will have to prove that
n^2+n+4 is divisible by 2 which also can be done by induction
If we want to use induction we have to break it into positive integers and negative integers
but in this example it is enough to consider non-negative integers because of odd function
Actually, you can prove the whole proposition using induction. You end up having to prove that 3n^2+3n+12 is divisible by 6, but this is easily done via induction again. It might not be the most elegant approach, but it works.
Since 11n = 12n - n, then
n^3 - 11n = n^3 - n + 12n.
12n is divisible by 6.
n^3 - n = n(n^2 - 1) = (n-1) n (n+1).
Three consecutive numbers are divisible by 6.
Therefore, n^3 - 11n is divisible by 6.