What does mathematical induction really look like?

►Follow me

►My Setup:

[zachstar]

A few people have mentioned a subtle mistake in that I should not be saying that for the second (inductive) step we assume our hypothesis for ANY value of n cause that's just what we are trying to prove anyway. But rather we must prove that if it's true for one positive integer n, then it it's true for the next. Just wanted to acknowledge that here, thanks for the correction you guys!

[HMotam-dnby]

Is this a math channel, an engineering channel or a superposition of the two?

[ShubhamRaj-muol]

Always wanted a better intuition for that

[jimboli]

Computer Scienctists: My time has come

[technoguyx]

I might point out that some of these examples may feel "artificial" to a student, as if specifically tailored to show the power of induction rather than problems that naturally appear in mathematics. But actually, there are many instances in which one needs an induction argument in both "pure" and "applied" maths: for instance in algebra, combinatorics and sometimes in analysis and differential equations (e.g. to find a power series solution Σc_kx^k for an ODE, you inductively find a expression for each c_k in the series). Great video as usual!

[stapler]

I'm told that to a philosopher, mathematical induction is actually a form of deduction.

[LucasSilva-utnm]

There is tiny bit "error" if I may say: In the method you assume that if it's true for N then that implies being true for N+1, not assume that it's true for N. In the second case you'd be assuming that what you're trying to prove is true, that is a circular argument. Besides that this a very cool visual way of learning, very easier than the way I learned.

[ChrisSutherlandPhys]

Induction is so important and a great visual explanation like this is desperately needed. Thank you Zach!!

[tonatiuhm.wiederhold]

Excellent video as always! I know it is subtle, but at 1:46, you SHOULD NOT be assuming the statement is true for any n, because that's what you want to prove, why bother with the rest of the argument if you already assume it's true for any n? What you want, is to prove that for any n, IF the statement works for THAT particular n, THEN it works for n+1 (these statements are not equivalent). Given that you showed it works for n=1, that completes the proof that it works for all n. Induction only works because for any case n+1 you want to check that works, it suffices to reduce it to the previous case n (precisely what your argument does). Any descending chain of natural numbers is finite, so all you need to do is check it works for the first one (in this case n=1) and that's why the rest works. I think this is the most common misconception when it comes to induction. The examples are great by the way :).

[eliyasne]

While i was watching the video i noticed that all of the inductive argument used in the geometry problems are also valid for 3d versions of these problems.

In fact they are valid for any dimensionality. 🤔

[michamaciaowicz]

In the Hanoi tower example it has been only shown, that it is possible to do with 2^(n-1) steps, but there was no proof, that it is the most efficient way.

[MA-jjth]

Thanks, this was super helpful, keep up the good work!

[NickDolgy]

This is very interesting! Thank you, Zach! And again, I am writing this first comment before the video is even published because I'm a patron on Patreon! What an honor! :-)

[RCSmiths]

As a visual learner, I gotta give it to ye! Cheers with the informative and high quality videos of concepts and ideas!

i just understood for the first time, that recursion is closely connected to induction. thanks for that!

[trust]

Thank you man! I think I get this principle now

[attila]

It's been 3 years but I only watched this video now...and wanted to say that as I watched I realized that you can leave a corner out, rotate them to get four empty space in the middle, fill that with another "L shape" and Zach started to do that so I feel very satisfied now.

[mitikox]

It's a cool introduction but there are a couple of points you missed:

1) you don't always have to start from the smallest n, sometimes n=1, 2, 3, 4 are exceptions, and n=5, 6, 7, ... is where induction can be applied
2) you didn't show strong induction - assuming not only it works for n=k, but for all n=1, 2, 3, ..., k and then proving it works for n=k+1 (aplies to some harder problems)
3) your minimal problem can't be solved by induction - by using induction you find a family of solutions for n=1, 2, 3, 4, .... but if you want minimality you have to show that any solution for n=k+1 has to use a solutionfor n=k. The other thing you can do is show all possible solutions for any n=k+1, only using the solution for n=k and then showing that at the beginning (n=const) you have obvious minimality. Otherwise you're only proving that a solution can not exceed number of moves, therefor a maxima for the problem
4) There are some cases where even/odd numbers matter. You can actually do induction on basis n=1, 2 and then prove "if n=k works => n=k+1 works too"
5) There are also some cool examples for multivariable induction. If a=1, b=1 works, and you prove that, given a=m, b=n you have a solution, when having a=m+1, b=n and a=m, b=n+1 it also works, then it works for all (a, b)
6) Induction is really common in graph proofs, so could've included one

Anyways, a great video for beginners, would love to see a second part!

[AlgyCuber]

for the first one shouldnt n = 0 work too? you just need one untiled square (the only square) and no L shape tiles which completes the tiling

[Cyberian_Khatru]

"this is probably gonna be the least obvious"

*proceeds to show the most obvious* lol