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
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.
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
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.
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.
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.
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 ?).
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.
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!) ...
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 ❤
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é)
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.
I used Modular arithmetic and calculated by substitution 0 mod 6, 1 mod 6, through 5 mod 6. It got me multiples of 6 for each case, but it was relatively longer and tedious than your solutions. Thank you for giving me an extra perspective!
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.
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.
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.
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.
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... 😃😃😃
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
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 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?
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
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.
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
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…
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
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.
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.
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.
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 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
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.
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.
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
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.
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.)
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.
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.
n³+11n = 12n + (n³-n) As the first term is a multiple of 6, we just need to show that (n³-n) is a multiple of 6. Any integer n can be written as 6m+r where m is some integer and r is 1,2,3,4 or 5 n³-n = (6m+r)³-6m-r = 6³m³+r³+3×6mr(6m+r) -6m-r = 6t + r³-r = 6t + r(r-1)(r+1) Now we just need to prove that the 2nd term is a multiple of 6. We can put r from 1 to 5 and show that.
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!!
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.
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.
You may also say that for any n it is either 3k or 3k+1 or 3k+2. Plug those into n(n²+1), then for 3k it's obvious, then both 3k+1 and 3k+2 when plugged into the the second part of expression produce 3 times an expression. So the whole expression is always divisible by 3.
The second method is so beautiful, Given a problem and a solution I enjoy generalising the problem to see if the same solution can be used to solve many problems. lets say c = 11 so problem become find all c where n^3 + c * n is divisible by 6. divisible by 2 mean c must be odd. using 1st method (because it is easier) we end up with: (k+1)^3 + ck +c = 3m + 3k^2 + 3k + c+1, so c+1 must be divisible by 3, but c+1 is even so c+1 must be divisible by 3 c = 6t -1 for any t in Z and when t = 0 the solution is trivial :)
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.
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
It's even because both terms have the same parity. It is a multiple of 3 because n is congruent to either 0, 1 or 2 mod 3, and plugging those in gives you 0, 12 and 30 respectively.
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
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
What I do is set up 3 sets of possible value of n, which one include all integer divisible by 3 (called it x for convenience) , x+1, and x+2, then expand and you will get 1. x(x²+11) 2. x(x²+3x+14)+12 3. x(x²+6x+23)+30 , then proof they are divisible by 3 as x mulitply anything plus a multiple of 3 is a multiple of 3, then proof it is divisible by 2 by rules of odd and even number
At 2:50 now. My thought is to fill in (6k + m) and calculate the result mod 6: let n = 6k + m which covers all integers if m in {0, 1, 2, 3, 4, 5}, then n^3 + 11n MOD 6 = (6k + m)^3 + 11(6k + m) MOD 6 = m^3 + 11m MOD 6. Sinds that is zero for m=0, 1, 2, 3, 4 and 5, it is always zero, hence n^3 + 11n is divisible by 6.
I just set k^3+11k=6M (where M is an integer) Then expanded (k+1)^3+11(k+1) into 6M+3k^2+3k+12, which is 6(M+2)+3(k^2+k). If k is odd, k^2+k is even If k is even, k^2+k is even So therefore k^2+k can be represented by 2N (where N is an integer) So the whole thing becomes 6(M+2)+6N 6(M+2+N) since M,N are integers, it is divisible by 6
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)
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)
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 :)
If we subtract 12 n times from a number, its divisibilty by 6 remains unchanged. n^3 + 11n ≡ n^3 - n (mod 6) = n(n^2 - 1) = (n-1)n((n+1) Three consectutive numbers must contain a mutliple of 3 and a multiple of 2, so their product must be divisible by 2x3 = 6. It doesn't take 16 minutes to figure that out.
It also does not take 16 minutes to determine you are impatient. If you want to do it the fast way, on your channel then I will give you a page view and you will also learn what it is like to tolerate viewers(like yourself) who nag at the creator for not doing it "their way" :)
@@MyOneFiftiethOfADollar Yeah, but the issue for me is not impatience. It's when creators take a trivial problem with a trivial solution and drag it out to 15 minutes by explaining every tiny obvious detail, or by taking the least efficient method of solution. I'm really envious of your capacity to tolerate those sort of antics.
n³ + 11n = n ⋅ (n² + 11) = n ⋅ (n² − 1 + 12) = n ⋅ (n² − 1) + 12n = n ⋅ (n − 1) ⋅ (n + 1) + 12n (n − 1) ⋅ n ⋅ (n + 1) is a product of three consecutive natural numbers. So, one of these three numbers is divisible by 3, and at least one of them is divisible by 2. Therefore, the whole product is divisible 2 and 3, and thus by 6. 12n is obviously divisible by 6, as 12 is a multiple of 6. And if both n ⋅ (n − 1) ⋅ (n + 1) and 12n are divisible by 6, their sum is divisible by 6 as well.
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
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.
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
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.
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.
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!
Just do n^3-n+12n and you get the answer
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 ?).
Never Stop Teaching!
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.
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!) ...
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 😅
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é)
I like this guy. The way he's passionate about maths shows in the content he makes :)
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.
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
I used Modular arithmetic and calculated by substitution 0 mod 6, 1 mod 6, through 5 mod 6. It got me multiples of 6 for each case, but it was relatively longer and tedious than your solutions. Thank you for giving me an extra perspective!
Excellent presentation! (And you have the cleanest blackboards I've ever seen!)
I love your videos ! It brings me back to my professors in the eighties.
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.
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
(n-1)n(n+1)+12n
Nice
But, how will he make a big video if you find such a simple proof?
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.
Beautiful solution!
A fantastic demonstration of mathematical induction, in particular.
Thank you!
GREATEST maths channel ik of. more people should discover you
love the way you explain things slowly and clearly
Guys, you might be using shortcuts but he is just doing it the most logical way. Well explained, appreciated
I didn't see Method 2 coming. Thanks for explaining it--very cool. I had better never stop learning!
Hey, man! I like how you always say "Never stop learning."
I hope my bad English won't lead to confusion, but what I love most about your videos is the beauty of your writing,
Bro your channel is awesome man keep up the good work man
Beautiful work! I look forward to seeing more. I was hoping to see you work with the modulus rules. They're currently mystifying me.
You just defied my expectations. Well done.
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
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.
For cleaner induction proof, instead of a new variable, you can use mod 3 = 0 notation.
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... 😃😃😃
This was a good refresher for me on using induction , and the second method requires a lot more phantasy... thanks!
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
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 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?
When i saw the method 2, i said: "THIS IS PURE ART" !!!
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
Amazing style of presentation!
This almost makes me want summer vacation to end just so I can go back to studying
Why can't you study during the summer?
@@johnvriezen4696 I meant in a school, but youre not wrong 🤔
Elegant presentation! Thanks for posting.
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.
If I had a teacher like him, with a mischievous smile and soothing voice, I would have made Math Olympiad team 😊
Just pay a gigolo. They may charge more for the soothing voice and mischievous smile, but would be money well spent for a guy with your needs.
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.
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 think modular arithmetic is the fastest way but it’s lovely to see other methods used!
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…
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.
The second method was really interesting, as my approach to solve this problem would always be mathematical induction from the beginning. Enjoyed it!
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.
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.
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.
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 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
very clean writing, is this using hagoromo chalk?
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.
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.
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
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)
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
"If you multiply 3 consecutive integers then the product is a multiple of 3"
Mindblown
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.)
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.
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.
n³+11n = 12n + (n³-n)
As the first term is a multiple of 6, we just need to show that (n³-n) is a multiple of 6.
Any integer n can be written as 6m+r where m is some integer and r is 1,2,3,4 or 5
n³-n
= (6m+r)³-6m-r
= 6³m³+r³+3×6mr(6m+r) -6m-r
= 6t + r³-r
= 6t + r(r-1)(r+1)
Now we just need to prove that the 2nd term is a multiple of 6. We can put r from 1 to 5 and show that.
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!!
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.
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.
You may also say that for any n it is either 3k or 3k+1 or 3k+2. Plug those into n(n²+1), then for 3k it's obvious, then both 3k+1 and 3k+2 when plugged into the the second part of expression produce 3 times an expression. So the whole expression is always divisible by 3.
On peut faire par disjonction des cas avec les differents restes par la division euclidienne de n par 6 (les congruences) non?
The second method is so beautiful,
Given a problem and a solution I enjoy generalising the problem to see if the same solution can be used to solve many problems.
lets say c = 11
so problem become find all c where n^3 + c * n is divisible by 6.
divisible by 2 mean c must be odd.
using 1st method (because it is easier) we end up with:
(k+1)^3 + ck +c = 3m + 3k^2 + 3k + c+1,
so c+1 must be divisible by 3,
but c+1 is even
so c+1 must be divisible by 3
c = 6t -1 for any t in Z
and when t = 0 the solution is trivial :)
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.
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
You can also show with the general form of n, the first case with n=3k is clear, then you take n=3k+1 or n=3k+2 and show that for them
Excellent demo of proof by induction.
It's even because both terms have the same parity. It is a multiple of 3 because n is congruent to either 0, 1 or 2 mod 3, and plugging those in gives you 0, 12 and 30 respectively.
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
Using the induction was very appropriate!
BTW if 6|P(n) = n^3 + 11n, 6|P(n+1) and
6|P(n+1) - P(n)
6|3n(n+1) + 12
6|12, 6|3n(n+1)
I really like your video and you happiness in solving math problem ❤
The simplest proof without much thought: Check for n = 0 to 5 whether mod(n^3 + 11*n, 6) = 0. Bingo.
You could also brute force with modular multiplication/addition with all 6 possible remainders when dividing n by 6
I can use modular arithmetic right?
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
Beautiful, thank you.
What I do is set up 3 sets of possible value of n, which one include all integer divisible by 3 (called it x for convenience) , x+1, and x+2, then expand and you will get 1. x(x²+11) 2. x(x²+3x+14)+12 3. x(x²+6x+23)+30 , then proof they are divisible by 3 as x mulitply anything plus a multiple of 3 is a multiple of 3, then proof it is divisible by 2 by rules of odd and even number
At 2:50 now. My thought is to fill in (6k + m) and calculate the result mod 6: let n = 6k + m which covers all integers if m in {0, 1, 2, 3, 4, 5}, then n^3 + 11n MOD 6 = (6k + m)^3 + 11(6k + m) MOD 6 = m^3 + 11m MOD 6. Sinds that is zero for m=0, 1, 2, 3, 4 and 5, it is always zero, hence n^3 + 11n is divisible by 6.
I just set k^3+11k=6M (where M is an integer)
Then expanded (k+1)^3+11(k+1)
into 6M+3k^2+3k+12, which is 6(M+2)+3(k^2+k).
If k is odd, k^2+k is even
If k is even, k^2+k is even
So therefore k^2+k can be represented by 2N (where N is an integer)
So the whole thing becomes
6(M+2)+6N
6(M+2+N) since M,N are integers, it is divisible by 6
That's cool and all, but can you answer me this: for what values "a". n^3+a*n^2 is always divisible by 6 if "n" is an integer
It's trivial. It suffices to check the cases where 0
And since it's so easy to show that it is always even, that allows you to simplify it and just check the cases where 0
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)
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)
can we use MI proving divisble by 6 directly at the beginning instead of 2 and 3?
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.
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 :)
If we subtract 12 n times from a number, its divisibilty by 6 remains unchanged.
n^3 + 11n ≡ n^3 - n (mod 6) = n(n^2 - 1) = (n-1)n((n+1)
Three consectutive numbers must contain a mutliple of 3 and a multiple of 2, so their product must be divisible by 2x3 = 6. It doesn't take 16 minutes to figure that out.
It also does not take 16 minutes to determine you are impatient.
If you want to do it the fast way, on your channel then I will give you a page view and you will also learn what it is like to tolerate viewers(like yourself) who nag at the creator for not doing it "their way" :)
@@MyOneFiftiethOfADollar Yeah, but the issue for me is not impatience. It's when creators take a trivial problem with a trivial solution and drag it out to 15 minutes by explaining every tiny obvious detail, or by taking the least efficient method of solution. I'm really envious of your capacity to tolerate those sort of antics.
n³ + 11n
= n ⋅ (n² + 11)
= n ⋅ (n² − 1 + 12)
= n ⋅ (n² − 1) + 12n
= n ⋅ (n − 1) ⋅ (n + 1) + 12n
(n − 1) ⋅ n ⋅ (n + 1) is a product of three consecutive natural numbers. So, one of these three numbers is divisible by 3, and at least one of them is divisible by 2. Therefore, the whole product is divisible 2 and 3, and thus by 6.
12n is obviously divisible by 6, as 12 is a multiple of 6.
And if both n ⋅ (n − 1) ⋅ (n + 1) and 12n are divisible by 6, their sum is divisible by 6 as well.