For curious: Induction works for well orderd set. If I am not wrong, here we used lexicograpihical orderding on ℕ², ie pairs of natural numbers: (a, b) ≤ (a', b') ⇔ a < a' or (a = a' and b ≤ b')
A fun two variable induction technique would be 1. Show that P(1,n) is true for all n. 2. Show that if P(m,n) is true, then P(m+1,n-1) is true. I wonder if there are some cool problems that could show if this approach.
Could we suppose P(m) is that for all n, the expression holds and the prove P(m+1)? I have seen something similar to that expression and looking at the table you showed I believe it would be like travelling through all the horizontal lines.
The idea behind the combinatorial proof is simple. Lets think about there being n coins and you want to divide them into m boxes. The way to do this is to insert m-1 sticks into the mix. Shuffle them. After you shuffle them, read off the coins based on the sticks that bound them. Let's say one possible outcome is c c | | c c c c | c | c| In the above, I have set n=8 coins and m=6 (ergo the 5 sticks ). Now the above is actually a solution to the original problem. Here x1=2, x2=0, x3=4, x5=1, x6=1. Notice that every shuffling of sticks and coins corresponds to a solution of the linear equation while every solution of the linear equation has a unique representation in terms of sticks and coins. Thus we need to count the no. of ways of shuffling the sticks and coins. This is (n+m-1)!/(n!(m-1)!) This is a standard result for shuffling groups of identical things.
Love this new series on induction tricks! Thanks a lot!
Thanks! A couple more left and I’ll make it a playlist
Great! Never seen this before, and that's what i like in your channel .learning new intresting math ideas!
Thanks yoav! More to come 😀
For curious: Induction works for well orderd set. If I am not wrong, here we used lexicograpihical orderding on ℕ², ie pairs of natural numbers:
(a, b) ≤ (a', b') ⇔ a < a' or (a = a' and b ≤ b')
I used it a lot but was a bit vague. Jazakallah Khairan brother to make things clear as day light!
Thank you Antor!
Do we need p(1,n) and p(m,1)? Is p(1,1) not enough?
The cascading effect from the inductive step seems to, at first glance, cover all cases.
A fun two variable induction technique would be
1. Show that P(1,n) is true for all n.
2. Show that if P(m,n) is true, then P(m+1,n-1) is true.
I wonder if there are some cool problems that could show if this approach.
Could we suppose P(m) is that for all n, the expression holds and the prove P(m+1)?
I have seen something similar to that expression and looking at the table you showed I believe it would be like travelling through all the horizontal lines.
Nice, these induction techniques are so cool!
So fun!
Interesting tehniques !!!!! Good job !!
Thanks Tony!
Very interesting ideas in an elementary topic.
Definitely Sandor
i like this channel
Thanks for this interesting lesson.
Would you please explain the combinatorial proof.
The idea behind the combinatorial proof is simple. Lets think about there being n coins and you want to divide them into m boxes. The way to do this is to insert m-1 sticks into the mix. Shuffle them. After you shuffle them, read off the coins based on the sticks that bound them. Let's say one possible outcome is
c c | | c c c c | c | c|
In the above, I have set n=8 coins and m=6 (ergo the 5 sticks ). Now the above is actually a solution to the original problem. Here x1=2, x2=0, x3=4, x5=1, x6=1.
Notice that every shuffling of sticks and coins corresponds to a solution of the linear equation while every solution of the linear equation has a unique representation in terms of sticks and coins. Thus we need to count the no. of ways of shuffling the sticks and coins. This is
(n+m-1)!/(n!(m-1)!)
This is a standard result for shuffling groups of identical things.
Nice video on Induction 🙂
Thanks! One coming soon today!
I love how the automated closed captions changed Prof Omar’s words from “combinatorics classes” to “common notorious classes”. Freudian slip! 😄
Math and cc fun!!
Figuring out different types of induction is basically like writing a recursive function im reverse.
Actually pretty much!
Thanks sir
Thanks!
1st!