Math Induction Trick RARELY taught in class!

[@riadsouissi]

That is a very nice proof of AM-GM worth remembering.

[@thedoublehelix5661]

Totally agree

[@aashsyed1277]

@@thedoublehelix5661 I LIKE YOU BECAUSE OF THAT

[@thedoublehelix5661]

@@aashsyed1277 w- what?

[@aashsyed1277]

@@thedoublehelix5661 GOOD

[@thedoublehelix5661]

The backwards part did involve some pretty slick moves. But it makes sense to choose the average of the previous numbers as the nth term

[@ProfOmarMath]

Ya after filming I realized it wasn’t as straightforward as I had in my head

[@yoav613]

I saw the proof forAMGM with regular induction and this forward backward induction is great !

[@ProfOmarMath]

Isn’t it? So much nicer!

[@bastiana.n.4277]

Wonderful! This makes me think that there has to be an even more powerful formulation of induction that enables to deduce other formulations (like the one you presented on the video) that might make solving a particular problem easier

[@ProfOmarMath]

There are several. We will see more in this series!

[@bastiana.n.4277]

@@ProfOmarMath Great, I'll wait patiently

[@SimchaWaldman]

WOW! Real art of induction proofs!

[@euqed]

Awesome ! One thing I'd really love to see is a proof of how all the variations of classical induction are logically equivalent

[@ProfOmarMath]

You can actually deduce some on your own! For example the 2n could have been replaced with 3n and things would still work. It’s kind of a directed graph problem with vertices being the natural numbers

[@georgedoran9299]

@@ProfOmarMath I’d imagine that there’s an infinity of possible induction techniques, you just need to ensure you cover all the cases.

[@coldsoup49]

How do you always find such cool topics??? I am in awe

[@ProfOmarMath]

Thanks coldsoup! Decades of experience! More to come 😍

[@physicsnovice656]

I remember when my calculus professor showed us this example during exercise sessions in 2010. He mentioned that he knew about it from Knuth's book Concrete Mathematics that I bought later, but I didn't go over it 100%.

[@ProfOmarMath]

Cool you get to revisit it!

[@hrs7305]

Nice ! Looking forward to more videos on induction

[@ProfOmarMath]

The next one is fun!

[@mathsandsciencechannel]

Well done sir. Love the video. Thanks

[@ProfOmarMath]

Thanks!

[@aashsyed1277]

@@ProfOmarMath SAME HERE!

[@danelrosen5461]

Awesome proof! New subscriber :D

[@ProfOmarMath]

Thanks Santiago! Enjoy the channel 😍

[@yoavshati]

You should prove by induction that proving by forward-backward induction works

[@ProfOmarMath]

😅

[@joseluishablutzelaceijas928]

This was REALLY cool! Thank you very much!

[@ProfOmarMath]

Definitely!

[@goodplacetostop2973]

As the saying almost goes, take a big jump forward to take a step back. 😝

[@ProfOmarMath]

This made me snort!!

[@aashsyed1277]

I love this channel

[@aashsyed1277]

I like you and Micheal penn

[@advaithkumar5966]

could you make a video on how to use this technique on the problem 'IMO Shortlist 2016 A1'? Thanks again

[@yassinezaoui4555]

Nice approach 8)

[@ProfOmarMath]

Thanks!

[@antormosabbir4750]

you can try bdmo 2020 higher secondary category's one of the problem. it needs this idea

[@ProfOmarMath]

Neat 😀

[@kanewilliams1653]

What software are you using Prof Omar? Love your red highlights that fade away.

[@ProfOmarMath]

Thanks Kane. I’m using GoodNotes on an iPad Pro!

[@ghimpugelu5375]

can someone explain why choosing an= (a1+a2+...+an-1)/(n-1) does not lose generality when proving p(n) -> p(n-1)?

[@bigjazbo9217]

I thought the same, but consider this: The AM-GM inequality for n numbers--where n is a power of 2--is proven true for any set of n positive numbers by forward induction. This is true for an arbitrary set of n positive numbers, so it will still be true even if one of those n numbers was specially constructed. Omar then demonstrated that for a special set of n numbers (n-1 arbitrary numbers plus one special number), the subset of n-1 arbitrary numbers also satisfies AM-GM. That means that if given any set of numbers where the number of elements is one less than a power of 2, we can add a special element to construct a special set of numbers of cardinality that is a power of 2, which we already proved by forward induction satisfies AM-GM, and which also implies that our given set of arbitrary numbers satisfies AM-GM. Now we know that all sets of numbers having cardinality one less than a power of 2 satisfies AM-GM. We can repeat the backwards induction process as far as necessary until we have proven AM-GM for all cardinalities between n and the next lower power of 2.

[@comuniunecuosho-campulbudi7611]

p(2ᵏ) true ⇔p(n) true, n=2ᵏ for any x₁,...,xₙ ⇒p(n) true even after we change xₙ (to a specially constructed one as we like) ⇒p(n-1) true so indeed p(n)⇒p(n-1)

[@sandorszabo2470]

Clever.

[@ProfOmarMath]

It’s fun!

[@tomkerruish2982]

Will you be covering transfinite induction?

[@ProfOmarMath]

I’m unsure yet because it might involve a long discussion of ordinals

[@tomkerruish2982]

@@ProfOmarMath You could do it for sets in general and only rely on the axiom of foundation, like how Conway did for his "one-line" proofs for the surreals. Namely, that if a property P of sets is such that, for any set x, if P holds for every element of x implies that P holds for x itself, then P holds for every set. As I write this, it occurs to me that it might be more appropriate for a course on set theory. I find it interesting, though, that there is no need for a base case, as P would necessarily hold for the empty set. Thank you for your response. I appreciate it.

[@petrotkach8757]

Forward step can be any, right? ( For example, P(5k) )

[@ProfOmarMath]

Yup!

[@Mrpallekuling]

This proof was discovered by the great Cauchy (1789-1857)

[@advaithkumar5966]

is this method also known as 'cauchy induction'?

[@ProfOmarMath]

Yes!

[@advaithkumar5966]

@@ProfOmarMath thanks for your response! Also, could you make a video on how to use this technique on the problem 'IMO Shortlist 2016 A1'?

[@aashsyed1277]

Nyc

[@chandankar5032]

Ah, the idea was to when one comes up with AM GM, it's easy to observe with assuming a+b/2 geq sqrt(ab) . We can do 4,6,,8... As any even number will be divided into to parts and base case can be applied. Similarly the other part, n positive numbers having am geq gm, well among thus n numbers, if we assume one is am of other n-1 s then we readily prove that for n-1 numbers. This the two statements. After the student observe these two, then you should tell them, the formal statement unless it's just checking and verifying. Another fun instance, say if I want to show identify permutation is even. Say if e has r cycles, it can be shown that it's essentially r-2 cycles, then r-4 cycles... I. E. P(r) implies P(r-2). So the crux of the matter is, there is a set at most countable, then by induction is just a way of saying one element generates other property s.t. all elements are covered. That property itself is equivalent to well ordering principle. Anyway, I'm glad I figure this chnanel (from Michael Penn)

[@robertveith6383]

(a + b)/2