Induction: Divisibility Proof example 1 (n³ + 3n² + 2n is divisible by 6)

[@syremusic_]

Such a great video. I find with proofs (for those in discrete math especially), it's about loading your mind up with a bunch of similar examples, and eventually things start to click 2-3 months down the road. Unfortunately by that point, exams are over :)

[@mariomenezes5974]

Oh, you are so right. I just had it happen to me.

[@gto11520]

amazing proof. cant believe this is taught in highschool. i am taking discrete math in college right now.

[@nelsonsiliezar3961]

From the USA ? We are so behind that we compete against 3rd world countries in education.

[@srersh05]

Im in india and we r learning this in highschool ksjsjdjd TT

[@davidgoulette2525]

Here is a fun proof of the statement WITHOUT induction. The expression factors as n(n+1)(n+2). Thus you have the product of three consecutive integers. Thus one of the integers must be even and one of the numbers must be divisible by 3. Thus the expression has 2 and 3 as prime factors. Hence the expression is divisible by 6.

[@TaseMagu]

Yep. That's the right explanation.

[@CarlitoProductions]

Currently doing data structures and algorithm and they threw us in to do induction, without any preparation or anything, so nobody knew what they were doing. I have an exam next week and this helps me 100% to get the jist of things. BIG thank you!

[@filiptomic3423]

you're so much better in explaining than our math proffesor. you explained in few minutes what he couldnt do at all he didnt even teach us the "assume that n=1" way !

[@harishbommarapu5521]

maybe u jus dont concentrate in class bro ahahaha

[@ENTJ616]

it is an unlikely condition haha. Sleeping in class is doing you wrong

[@Dcmazters]

It’s not exactly assume n=1, it is show/test that the statement is true for n=1. Induction is based off the logic that, since it is true for the “base case” (usually n=1), and assuming it is true for n=k, IF you can show that n=k+1 is true by connecting with the n=k, there is nothing that stops your k value being 1, which results in proving every subsequent number.

[@integralCalculus]

Great video! Sometimes, though, mathematical induction (MI) just makes the proof more complicated. In this specific example, the given expression is factorizable into n(n+1)(n+2). Now, since n is a natural no., either n itself or n+1 is even. Also, it's not hard to see that for any three consecutive natural numbers, exactly one has to be divisible by 3. This result is actually generalizable to the statement "the product of any k consecutive integers is divisible by k", which can again be proved by some effort but without resorting to MI. So, we have the given expression divisible by 2 and 3, which are coprime to each other. Therefore, the expression itself is divisible by 2X3 i.e 6.

[@ClaytheOwen]

Thanks for the lesson Eddie! It's always good to have a fresh perspective to compliment what I do in class. This was well taught, highly recommend.

[@DerangedIntellectual9]

i used to think induction was ugly and a curse to us first-year engineering students, but after watching this video i see that there is some beauty to its process. thank you for helping me understand the topic sir.

[@josephhernberg9478]

Oh man, my FOCS professor is good, but hasn't gotten to this part yet. Doing the homework now and you've helped me on something I thought was nearly impossible, thank you man.

[@ranjithraj36]

Highly Loaded with energy levels sir superb teaching

[@jadkousa294]

What a legend!

[@palakbiyani8695]

Totally loved that proof!

[@F7FD]

2020 and he still explains better than my uni doctors

[@samanthazelada2950]

Love your channel!

[@kwanelephakathi1696]

Man you are just great!

[@baspalinckx5055]

Thank you so much! The using my brain part had me

[@onepercentmilk5440]

i wish i cud get as excited as this dude

[@amardexter9966]

I know it's an example for induction course, but seems like too much work when it could be easily solved by modular arithmetic or simple logic: n^3 + 3n^2 + 2n = n(n+1)(n+2) => from three consecutive integers one of them has to be divisible by 2 and same for 3, hence the polynomial is divisible by 6. Idk, sometimes induction seems to be messy and almost feels like brute-forcing to solution

[@AceOfHearts001]

really nicely explained as always.

[@MrJ3]

It only took 3 or 4 videos of yours to convince me to subscribe. Color me impressed!

[@aldanstomer]

thanks for this I'm able to this in my head now

[@nathanbeer3338]

Good idea at the end of solving it. My less creative way was making another induction on (3k^2 + 9k) whether it is divisible by 6 which worked as well.

[@albertohart5334]

Couldn’t you just restart and prove that 3k^2 + 9k + 6 is divisible by six by proof of induction

[@akshat_shukla00]

Yup, Also, u could just prove 3k²+9k is divisible by 6 Via induction.

[@That_One_Guy...]

3k^2 + 9k + 6 = 3(k^2 + 3k + 6) = 3a Want to proof 3a divisible by 6 k^3 + 3k^2 + 2k = k(k^2 + 3k + 2) = ka 6p = ka a = 6 * p/k 3a = 6 * 3p/k No matter what is the value of p and k is, 3a is still divisible by 6 (because it's a value multiplied by 6) Q. E. D

[@Westerword]

Hi mr woo, I was just wondering of you have uploaded any perms and combination videos? I can't seem to find them I.e counting unordered pairs, counting ordered selections etc. thanks:)

[@PBJJJ]

Thank you Eddie!!

[@andrescabrera6097]

Funny teacher and you’re great

[@harvardford8752]

why did i not see your vids sooner I WAS HAVING TROUBLE FOR SO LONG OMG

[@cindygatica2135]

I wish my teacher were like you haha

[@NicaKasende]

Thank u so much sir!!

[@xDMrGarrison]

Wow pretty cool :)

[@shujamukhtar4563]

can someone explain to me the k(k+3) thing? Also, can someone tell me the logic behind the 6P? why did he keep the statement in step 2 equal to 6P? Thanks.

[@asimami3061]

Can anyone tell me that is this chapter taught in year 11 Specilist maths or year 12 specialist maths in Australia. Please reply me asap

[@virtuousjoffrey8022]

This is great stuff ,love your initiative. Where do you teach ?

[@knightwik]

he teaches at cherrybook tech school sydney, nsw

[@ballinbadger8635]

Would it not be possible to do a proof within a proof for the statement 3k(k+3)=6M, thereby proving that all of 6M+6+3K(K+3) is indeed divisible by 6 for any value of n?

[@Alexj_movieguy]

I was actually thinking the same thing! It would probably help in an exam to show them that it’s true and not just an assumption (would be a relatively quick proof too).

[@user-oi2kc1bb9x]

Hey Mr Woo, can't this question be done by factorising the assumption into k(k+1)(k+2)=6M , hence (k+1)(k+2)=6M/k, sub that expression when proving for n=k+1, then factorise the 6 out of it, resulting in LHS=6(M+3M/k) which is divisible by 6. Or am I missing anything?

[@saleemismailkugu2426]

question. I'm having difficulties here trying to solve it. x-12, 3x-2/7, 3x+2/7, Bx+6. What is the value of B.

[@GodlyOne123]

Do you by any chance teach or tutor Calculus 3 or Linear Algebra?

[@danielglass2937]

i did this without fancy maths you have to remember by factorising the original function -> n(n+1)(n+2) therefore n=k -> k(k+1)(k+2) = 6P (k+1)(k+2)=6P/k * then n=k+1 therefore (k+1)(k+2)(k+3) = 6M * sub in the n=k equation LHS = (6P/k)(k+3) LHS = 6P +18Pk^-1 =6(P+3Pk^-1) therefore divisible by 6

[@ccas8719]

Would you not need to also prove that [P(k+3)]/k is an integer? I tried this method and stopped at that point because the statement is not true.

[@justvince4158]

what I did was I didnt combine the 3k and 6k so I had an extra 3(k^2 + k) this holds true iff (k^2 + k) is divisible by 2 (or even).... what I did is to prove it again using another induction. is that acceptable?

[@indianapacers759]

Yes, I believe so, because k^2+k is k(k+1), which is an odd number times an even number, which is always divisible by two (similar to what he showed in the video). Thus, you have 3(2C), where 2C is equal to k(k+1) and C is a positive integer, which is 6C, a number divisible by 6.

[@hathawayamato]

I think this exact question came up in the IB HL math exam this year lol

[@mannyheffley9551]

Shun Yat Cheung it came in my class 9th Fiitjee exam if you know what it is.A similar one tho.

[@_godsl4yer_]

IB gang :)

[@mannyheffley9551]

@Ignited TNT abe laude

[@mbongosfiso6193]

I'm amazed

[@arifamohammadi2698]

thank you so much

[@alvinjoffy3528]

this was asked in my 11th model exam

[@Mathelite-ii4hd]

another proof is : n^3+3n^2+2n=n(n^2+3n+2)=n(n+1)(n+2) and we know that n(n+1) is always divisible by 2 and also n(n+1)(n+2) is also always divisible by 3 and (2,3)=1 so n(n+1)(n+2)=n^3+3n^2+2n is divisible by 6.

[@EdwardFectory]

Nice

[@rotemlv]

It's actually true for all k, non-negative or negative (zero is a whole number in Z).

[@aleksajanic4414]

At the point where we have 6P + 6 + 3k^2 + 9k, cant we just multiply the whole equation by 2? So we get 12P + 12 + 6k^2 + 18k and then we can easily extract the 6 in the front which gets us to 6(2P + 2 + k^2 + 3k) and thats devisible by 6. But i'm not sure if it's allowed to multiply the whole thing by 2 at that point, does anyone know for certain?

[@williamperezhernandez7331]

Multiplying by 2 just proves it was divisible by 3, not by 6. Example, if we multiply 15 by 2 we get 30, which is divisible by 6, but 6 does not divide 15.

[@Lemon-ej4pn]

If you multiply LHS by 2 then will have to multiply RHS i.e. 6Q by 2 too so it really doesn't make any difference

[@mrhatman675]

Hmmm or you could do this way instaid much easier and faster n^3+3n^2+2n=n×{n^2+3n+2}=n×{n+1}×{n+2} now since we know that one of the terms must be 2k and if we say n=3a+b where 0≤b≤2 then n×{n+1}×{n+2}={3a+b}×{3a+b+1}×{3a+b+2} now just replace b with 0,1,2 respectivelly and we find that each time one of the terms is 3c and also at least one of the terms must be 2k from that we can deduce that this is always 6c

[@TaseMagu]

It's much simpler than that. Since you have a product of 3 consecutive numbers, at least one is divisible by 2 and at least one is divisible by 3 => so the entire result must be divisible by 6

[@mrhatman675]

@@TaseMagu I mean this isn t really a proof but a fact I basically proved the fact that you are stating

[@TaseMagu]

@@mrhatman675 What do you mean it's not a proof ? 3 consecutive terms a,b,c at east one is even a = 2*x and at least one is divisible by 3, b=3*y (could be the same "a" divisible by 3 which in turn means chosen "x" divisible by "3" which means "a" directly divisible by 6) => a*b*c= 6*x*y*c divisible by 6. That's why I said you complicated yourself. The same way you said one must be 2k because at least one is even, you can always say one is 3m because there's 3 consecutive and at least one is divisible by 3.

[@TaseMagu]

O well.... if you mean you kind of demonstrate that one of 3 consecutive numbers is divisible by 3. But then you assume we know one is even (2k). How do we know ? Either you prove both or assume both as common knowledge. It doesn't really make sense to prove just one and assume the other. And better proof is done by reductio ad absurdum. Tn= 3k+1 or Tn =3k+2 => T(n+1)= (Tn)+1... T(n+2)=(Tn)+2...... and you get a contradiction in each case.

[@peterhyland1204]

An alternative proof: (n^3 + 3n^2 + 2n) factors to n(n + 1)(n + 2), I hope. Each of these factors can be either 1 or 0 in mod2. Similarly, each can be equal to 0,1 or 2 in mod3. No two factors can be the same in mod3 as they differ by at most 2 and at least 1 and similarly, not all can be the same in mod2. So, by the pigeonhole principle at least one is 0 in each modulus therefore, the entire expression is divisible by 6 for all integers.

[@Sbigsla]

Could also prove that the left over part is divisible by 2 using induction !

[@franeagle]

You mean divisible by 6

[@raghuls5914]

Why can't we factorise it into n(n+1)(n+2) and use division algorithm

[@Kindiakan]

valid proof from a number theoretic pov but irrelevant to the topic of math induction

[@disciplinenepal5081]

good

[@chrisdesrochers9062]

Doesn't this factor to n(n+1)(n+2). If so, necessarily it must have a factor of 2 and 3. Thus, there you go. It's divisible by six. Or, I really missed something and that could be embarrassing? :) Either way, that's a thought that I had. But, if that is true, it doesn't mean it's not a good exercise in Mathematical Induction, something I unfortunately seem to get crossed up from time to time.

[@picnicbros]

My professor said, nah bro, you have to also prove k(k + 3) is even, you cant just say that it is even (another induction?)

[@azmath2059]

hi Eddie. it's best to do a second induction to prove that last expression is actually divisible by 6.your explanation is a little hard to follow

[@avananana]

This is probably the easiest proof you can find on this problem lol.

[@tilashini3124]

how u get the 6p?

[@joshuatamer9500]

He introduced p. He assumed S(k) = 6p, which assumed the fact that the polynomial is divisible by 6 (any factors of 6 are divisible by 6)

[@fayjaz]

i am stuck on some divisibility questions, if you could please help me i would be very thankful to you. 2^(n+2) + 3^(2n+1) is divisible by 7 for all integers n>=1 i am stuck on proving n=k+1 :( because i dont know how to subtitute [7P(which is sum of k-->Sk)] into the proving n=k+1 part

[@shannon4303]

+Fa iza hi I know this was a long time ago but I am currently facing the exact same problem. Did you ever find out how to solve this?

[@fayjaz]

shannon ill try to do it again and see if i get the answer :)

[@fayjaz]

shannon go to this group if you have facebook and hopefully theyll be able to help you facebook.com/groups/1611000299184053/ i dont remember how i did it im sorry

[@JohnSmith-hj8kv]

Oh, I just inducted twice to get the proof but I suppose this is more elegant.

[@Sbigsla]

John Smith I did too

[@Sbigsla]

And I actually find that 2 inductions is a lot more beautiful than righting all of the text showing that 3k(k+3) is even But thinking about it is definitely elegant

[@rasmilamichhane5850]

How can you say k has to be odd or even? but not odd,odd and even,even. integer can be both even and odd.

[@Vlayer]

+nepLI chori If k is even, then (k+3) has to be odd because of the 3(odd number) added to it. Likewise if k is odd, then (k+3) has to be even because of the 3 added to it. even# + odd# = odd# and odd# + odd# = even#.

[@rasmilamichhane5850]

+Vlayer I was misunderstanding k (k+1) these two k is different value at same time odd(even+3), which is not possible and didn't thought he was talking about k and k+3. k(k+3) must be even because even(even+3)=even*odd=even and odd(odd+3)=odd*even= even.

[@zhaoningding7599]

why u exclude n=0?

[@Fightclub1995]

0 is divisible by 6

[@XTC2525]

This could be proven in a few lines without induction, but I understand the whole point is to teach induction so this is still a good video

[@maxbranco7321]

Yo, can I just factor out the 6 out of 3K^2 + 9K + 6 and get 6(1/2 k^2 + 3/2 k + 1)? I wouldn't have thought of the odds evens stuff

[@djbokasuja]

I'm not fluent in English, but I can understand a lot. When you put the 2R, I couldn't follow anymore. I just didn't understand why 2R and not anything else like B or S. Why 2xR?

[@elegiggle6524]

3k(k+1) is the same thing as 3 x k x (k + 1). if k is an even number, (k + 1) would be an odd number. so you would have 3 x (even number) x (odd number). if k is an odd number, (k+1) would be an even number. so you would have 3 x (odd number) x (even number). an even number multiplied by an odd number is always even, this means that for any k in the set of Natural numbers, k(k + 1) is even. with this fact, he represents k(k+1) as an even number 2R. (2R is used in math to represent an arbitrary even number. you don't have to use the variable R, you can use any letter you like).

[@patrikmuller6735]

I had trouble with understanding this 2R stuff too but now it's clear. Thank you for fenomenal explanation Ele!

[@alleg0ry]

MATH HL NIGGAS KNOW THE STRUGGLE INSHALLAH

[@Illu07]

Why does he uses Z+ instead of just N?

[@elegiggle6524]

From Wikipedia: Some definitions, including the standard ISO 80000-2, begin the natural numbers with 0, corresponding to the non-negative integers 0, 1, 2, 3, …, whereas others start with 1, corresponding to the positive integers 1, 2, 3, …. so sometimes people use 0 in the set of natural numbers. using Z+ will avoid this confusion.

[@eiskola7811]

nahh number theory too hard for me i’ll stick with calculus

[@mi-tw2yr]

Any indian?

[@knightwik]

yeah... hi!