The Intuition Behind Proof by Induction

We prove that a tree on n vertices has n-1 edges (the terms are introduced in the video). This serves as a motivational problem for the method of proof called induction. First, we overview the idea of the proof. Only after we develop a full argument do we formalize the proof in the standard format of induction.

[@TooManyPBJs]

I'm taking a graduate algorithms course, and we were expected to know discrete for the first week. This video was a blessing. Thank you.

[@Bread4Life62]

"I hate windows" LOL. Thank you for the great explanation of induction. One of my students was thoroughly confused (so was I).

[@Zachariah-Abueg]

This is one of the best videos on the entire internet. I loved this intuition so much. Thank you, thank you, thank you. I really enjoyed how you motivated it from a tree problem that anyone can understand and used the intuitive notion of building trees one by one to eventually formalize what induction is and what it can do for us. Wow. Thank you. I'm honored to have watched this.

[@luisfernando262]

What a blessing, I needed just a bit more detail into this process. Thank you so much!

[@Autom_te]

This is examplar of how to build intuition on a subject. Start very basic, and _slowly_ build upwards with an example. I wish more people assumed this basic style when explaining.

[@saakshimalhotra3926]

not me whispering multiple times "Damn, she is so cool !"

[@TanishqRulania]

fr

[@sandhyaranidash2429]

If you could teach mathematics/logic teachers on how to teach concepts, that will spark interest in Mathematics/logical thinking among millions of students around the world. Another fantastic video, huge thank you from one of your fans :)

[@arnabsarma5568]

I love u for the way u proved it.. this is the best teaching bi have ever received

[@basedworldsk8]

Excellent explanation this made it so simple.

[@d.riedijk3443]

Very well explained, thanks!

[@mitchellasuter]

If one separates T into T_1 and T_2 where |V_1| > 1 and |V_2| > 1, are we invoking Strong Induction?

[@kal5211]

Excellent.

[@karishmakunwar7795]

so so good..well done mam

[@nelsonthekinger]

well done mademoiselle

[@brandm5176]

This is the one of the best! 18:33

[@shimulbhattacharjee5137]

Superb explanation.

[@gonzalob.3340]

Great video!

[@ina5503]

Thank you!

[@dell2able]

Good video!

[@tashp]

Amazing video thank you!

[@BrienDunn]

Nice!

[@soumyajitsarkar2372]

So basically , Induction can be thought of as an Recursive proof technique.n call n-1,n-1 calls n-2 ....and ultimately 2 calls 1 and then the function returns ,till n is reached . Beautiful .

[@michaelmika9665]

i just subscribe