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
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.
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!) ...
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.
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.
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 ❤
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.
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'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.
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.
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 ?).
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
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 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... 😃😃😃
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.
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❤❤❤
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 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
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.
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 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
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.
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 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.
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.
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 :)
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
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
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.
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)
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.
*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.)
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)
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.
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
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 :)
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 method to solve this was close to the method 2 in this video: A number divisible by 6 is divisible by 2 AND 3. G(n) = n(n+1)(n+2) = n³+3n²+2n is divisible by 6, because one of the factors much be divisible by 3 and at least one of the factors must be even. F(n) = n³+11n is divisible by 6, if the difference of G(n) and F(n) is divisible by 6: H(n) = G(n) - F(n) = (n³+3n²+2n) - (n³+11n) = 3n²-9n = 3n(n-3). If n is even, 3n is divisible by 6. If n is odd, 3(n-3) is divisible by 6. Hence n³+11n is divisible by 6 for all integers.
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 😢
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! 😀😀
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.)
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.
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…
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)
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.
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
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.
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
I did it this way. 0^3 is congruent to 0 mod 3, 1^3 ict 1 mod 3 and 2^3 ict 2 mod 3. 11*0 igt 0 mod 3, 11*1 ict 2 mod 3 and 11*2 ict 1 mod 3. So, using 1 as the example which also applies to 0 and 2, 1^3 + 11(1) is congruent to 1 mod 3 plus 2 mod 3, which is 0 mod 3. Thus k^2 + 11k is always divisible by 3 because all integers are 0, 1 or 2 mod 3 and in each case the terms sum to 0 mod 3.
n^3 + 11n = n(n^2+11) In order to be divisible by 6 a number must be visible by 2 and 3. If n is even then n(n^2+11) is an even number multiplied by an integer, which results in an even number. If n is odd n^2+11, then n^2 will be odd as the product of 2 odd numbers and adding 11 to it will be the sum of 2 odd numbers, which is even. Thus n(n^2+11) is always even. Let's break down n based on it's remainder modulo 3. Note that 11 == 2 mod 3. n == 0 mod 3 then the entire product is disable by 3. n == 1 mod 3 then n^2 == 1 mod 3 This the product's remainder after division by 3 is 1(1+2) = 3 == 0 mod 3 n == 2 == -1 mod 3 then n^2 == 1 mod 3. This the product's remainder after division by 3 is -1(1+2) = -3 == 0 mod 3
For me, I did it a very long-winded way frankly. Let P_n be the proposition that n^3 + 11n is divisible by 6. First, prove P_1 is true P_1 = 1^3 + 11(1) = 1 + 11 = 12 = 2 * 6 So P_1 is true. Now let P_n be true for some integer k, that k^3 + 11k = 6s, where s is some integer [Or that k^3 + 11k is divisible by 6] We prove P_k+1 is true P_k+1 = (k+1)^3 + 11(k+1) = k^3 + 3k^2 + 3k + 1 + 11k + 1 = (k^3 + 11k) + 3k^2 + 3k + 12 The component k^3 + 11k are divisible by 6 [assumed as initial condition], and so is 12. So we prove that 3k^2 + 3k is also a multiple of 6 for all k If k is odd, then 3[(2p+1)^2 + (2p+1)] = 3[4p^2 + 4p + 1 + 2p + 1] = 3[4p^2 + 6p + 2] = 6[2p^2 + 3p + 1] If k is even, then 3[(2p)^2 + 2p] = 3[4p^2 + 2p] = 6[2p^2 + 1] [Another way is that if k is odd, then 3(odd^2 + odd) = 3(odd + odd) = 3(even) = 6(something), and if k is even, then 3(even^2 + even) = 3(even + even) = 3(even) = 6(something)] So 3k^2 + 3k is divisible by 6 for all k. Hence, all the components of P_k+1 are divisible by 6, proving that it is divisible by 6. Since P_1 is true, and P_k => P_k+1 is true, then by mathematician induction P_n is true for all integers n, and hence n^3 + 11n is divisible by 6 for all integers n.
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.
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 :)
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
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!
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!) ...
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.
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 are an amazing guy also you have a deep passion for Mathematics.Keep going you will oneday reach 1Million subscribers.
Love 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
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 😅
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.
GREATEST maths channel ik of. more people should discover you
Never Stop Teaching!
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é)
Beautiful solution!
A fantastic demonstration of mathematical induction, in particular.
Thank you!
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.
Excellent presentation! (And you have the cleanest blackboards I've ever seen!)
I like this guy. The way he's passionate about maths shows in the content he makes :)
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 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 love your videos ! It brings me back to my professors in the eighties.
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 ?).
I hope my bad English won't lead to confusion, but what I love most about your videos is the beauty of your writing,
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 didn't see Method 2 coming. Thanks for explaining it--very cool. I had better never stop learning!
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
This was a good refresher for me on using induction , and the second method requires a lot more phantasy... thanks!
love the way you explain things slowly and clearly
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!!
The second method was really interesting, as my approach to solve this problem would always be mathematical induction from the beginning. Enjoyed it!
Beautiful work! I look forward to seeing more. I was hoping to see you work with the modulus rules. They're currently mystifying me.
I really like your video and you happiness in solving math problem ❤
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... 😃😃😃
You just defied my expectations. Well done.
(n-1)n(n+1)+12n
Nice
But, how will he make a big video if you find such a simple proof?
Hey, man! I like how you always say "Never stop learning."
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.
Elegant presentation! Thanks for posting.
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❤❤❤
For cleaner induction proof, instead of a new variable, you can use mod 3 = 0 notation.
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.
Bro your channel is awesome man keep up the good work man
very clean writing, is this using hagoromo chalk?
Amazing style of presentation!
When i saw the method 2, i said: "THIS IS PURE ART" !!!
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
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
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.
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
Nice problem and great solution, just please, light a little bit more the studio.very dark, no lights.
Thank you for good video👍
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
Mathematical induction such a beautiful amd powerful tool
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.
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.
Excellent demo of proof by induction.
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.
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.
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 :)
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.
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
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
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.
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)
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.
*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ì
Nice question
But got solved easily
(x+1)(x+2)(x+3) is always divisible by 3 and 2 both, Thus by 6 also
X³+ 11x is part of above
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)
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.
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
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 :)
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 method to solve this was close to the method 2 in this video:
A number divisible by 6 is divisible by 2 AND 3. G(n) = n(n+1)(n+2) = n³+3n²+2n is divisible by 6, because one of the factors much be divisible by 3 and at least one of the factors must be even. F(n) = n³+11n is divisible by 6, if the difference of G(n) and F(n) is divisible by 6:
H(n) = G(n) - F(n) = (n³+3n²+2n) - (n³+11n) = 3n²-9n = 3n(n-3).
If n is even, 3n is divisible by 6.
If n is odd, 3(n-3) is divisible by 6.
Hence n³+11n is divisible by 6 for all integers.
What a clear explanation. Thanks.
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 😢
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)
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! 😀😀
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.)
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 !
Beautiful, thank you.
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…
Wow that second method was magic!!
The simplest proof without much thought: Check for n = 0 to 5 whether mod(n^3 + 11*n, 6) = 0. Bingo.
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)
I love that 2 sec cunning smile at 14:49
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
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.
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
Bravo for the 2nd solution!
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 🤔
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.
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.
I did it this way. 0^3 is congruent to 0 mod 3, 1^3 ict 1 mod 3 and 2^3 ict 2 mod 3. 11*0 igt 0 mod 3, 11*1 ict 2 mod 3 and 11*2 ict 1 mod 3. So, using 1 as the example which also applies to 0 and 2, 1^3 + 11(1) is congruent to 1 mod 3 plus 2 mod 3, which is 0 mod 3. Thus k^2 + 11k is always divisible by 3 because all integers are 0, 1 or 2 mod 3 and in each case the terms sum to 0 mod 3.
n^3 + 11n = n(n^2+11)
In order to be divisible by 6 a number must be visible by 2 and 3.
If n is even then
n(n^2+11) is an even number multiplied by an integer, which results in an even number.
If n is odd
n^2+11, then n^2 will be odd as the product of 2 odd numbers and adding 11 to it will be the sum of 2 odd numbers, which is even.
Thus n(n^2+11) is always even.
Let's break down n based on it's remainder modulo 3. Note that 11 == 2 mod 3.
n == 0 mod 3 then the entire product is disable by 3.
n == 1 mod 3 then n^2 == 1 mod 3
This the product's remainder after division by 3 is
1(1+2) = 3 == 0 mod 3
n == 2 == -1 mod 3 then n^2 == 1 mod 3.
This the product's remainder after division by 3 is
-1(1+2) = -3 == 0 mod 3
Wow - Method 2! Good revision as a bonus
For me, I did it a very long-winded way frankly.
Let P_n be the proposition that n^3 + 11n is divisible by 6.
First, prove P_1 is true
P_1 = 1^3 + 11(1) = 1 + 11 = 12 = 2 * 6
So P_1 is true.
Now let P_n be true for some integer k, that
k^3 + 11k = 6s, where s is some integer [Or that k^3 + 11k is divisible by 6]
We prove P_k+1 is true
P_k+1 = (k+1)^3 + 11(k+1)
= k^3 + 3k^2 + 3k + 1 + 11k + 1
= (k^3 + 11k) + 3k^2 + 3k + 12
The component k^3 + 11k are divisible by 6 [assumed as initial condition], and so is 12. So we prove that 3k^2 + 3k is also a multiple of 6 for all k
If k is odd, then 3[(2p+1)^2 + (2p+1)] = 3[4p^2 + 4p + 1 + 2p + 1] = 3[4p^2 + 6p + 2] = 6[2p^2 + 3p + 1]
If k is even, then 3[(2p)^2 + 2p] = 3[4p^2 + 2p] = 6[2p^2 + 1]
[Another way is that if k is odd, then 3(odd^2 + odd) = 3(odd + odd) = 3(even) = 6(something), and if k is even, then 3(even^2 + even) = 3(even + even) = 3(even) = 6(something)]
So 3k^2 + 3k is divisible by 6 for all k. Hence, all the components of P_k+1 are divisible by 6, proving that it is divisible by 6.
Since P_1 is true, and P_k => P_k+1 is true, then by mathematician induction P_n is true for all integers n, and hence n^3 + 11n is divisible by 6 for all integers n.
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.
It's trivial. It suffices to check the cases where 0
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 :)