Strong induction is just a special case of induction. Replace the statement P(k) in normal induction with the statement Q(k)=P(n) for n=1 to k. And that's a good place to stop.
Example 1 For the IH, you should assume k>=2 not 1. The reason is when you apply it to P(k-1), you need to have that k-1 less than or equal to k which is cool, but you also need to have it greater than or equal to 1. The thing is if you assume k>=1, you will not be able to use the IH on P(k-1). In other words, you need 1
I feel like a direct proof is cleaner for the 2nd example. Show 6 | n³ - n n³ - n = n(n² - 1) Easy parity argument shows that exactly one of those factors must be divisible by 2. Also, one of those factors must be divisible by 3. Case 3|n: we're done. Otherwise n≡±1(mod 3), so n²≡1, n²-1≡0, and we're done. It's divisible by 2 & 3, so it's divisible by 6. (edit: I get that the point is to demonstrate the technique, not these specific results. This just seemed like a weird fit for the method being demonstrated.) The graph example was nice, though. Could just use weak induction, but strong induction saves the headache of showing a leaf must exist.
Use Fermat’s little theorem to prove divisibility by 3, and recognize that n^3-n=n(n^2-1) is also divisible by 2 since n and n^2-1 have opposite parity.
You are all completely correct, although when learning induction it is useful to apply it to questions like this that may be solved easier with these other methods.
I feel 6/n^3-n is easiest to prove as follows for n≥4 n^3-n =n(n^2-1) =n(n+1)(n-1) =Product of 3 consecutive integers =Divisible by 3! = Divisible by 6 Hence proved.
Ex. 2: I put strong induction into your induction so you can use divisibility properties of consecutive integers as part of a proof involving strong induction while not using divisibility properties of consecutive integers as a proof itself. (not against it btw, just looks fun)
x&y = xy/x+y = 2y (when x != 0) So "x&" can to taken as the unary doubling operator. Your expression is 22021 with "x&" applied (22021-22 = 21999) times, so 22021 * 2^21999. Make rigorous via induction. If, on the other hand, x&y = xy/(x+y), that gets interesting... Interesting enough to think that it might be a homework problem.
Hi pal, it is not my mind, but I think you could be a little more kind with your followers. I mean, give an answer or say hello. I know you are happy with maths.... you are brillant anyway. Thanks for all that knowledge.
Strong induction is just a special case of induction. Replace the statement P(k) in normal induction with the statement Q(k)=P(n) for n=1 to k. And that's a good place to stop.
I'm so happy that I can understand the whole thing he's talking in this video. 😄
Me too!
Example 1
For the IH, you should assume k>=2 not 1. The reason is when you apply it to P(k-1), you need to have that k-1 less than or equal to k which is cool, but you also need to have it greater than or equal to 1. The thing is if you assume k>=1, you will not be able to use the IH on P(k-1). In other words, you need 1
I very much enjoy the errors that were left in. It's fun to see you stopping your speech and then retake it from the beginning of the sentence.
I feel like a direct proof is cleaner for the 2nd example.
Show 6 | n³ - n
n³ - n = n(n² - 1)
Easy parity argument shows that exactly one of those factors must be divisible by 2.
Also, one of those factors must be divisible by 3. Case 3|n: we're done. Otherwise n≡±1(mod 3), so n²≡1, n²-1≡0, and we're done.
It's divisible by 2 & 3, so it's divisible by 6.
(edit: I get that the point is to demonstrate the technique, not these specific results. This just seemed like a weird fit for the method being demonstrated.)
The graph example was nice, though. Could just use weak induction, but strong induction saves the headache of showing a leaf must exist.
Use Fermat’s little theorem to prove divisibility by 3, and recognize that n^3-n=n(n^2-1) is also divisible by 2 since n and n^2-1 have opposite parity.
@David Schmitz D'oh! That's so much more elegant and such a small step to take! I was blinded by my proof being "good enough."
You are all completely correct, although when learning induction it is useful to apply it to questions like this that may be solved easier with these other methods.
How do you get otherwise n≡±1(mod 3)?
@@MichaelPennMath How do you get otherwise n≡±1(mod 3)?
Another great video. Thank you Prof. Penn!
I’m still stuck trying to prove this one thing. I accidentally let my base case go from 1 to infinity, it’s taking forever.
I know, I know, keep going, and you'll get there. Don't give up 😬👍🏻
You've come a long way from the time I first watched your videos. Now you have the verified sign!
Thanks so much!
Good stuff. Very good review
I feel 6/n^3-n is easiest to prove as follows for n≥4
n^3-n
=n(n^2-1)
=n(n+1)(n-1)
=Product of 3 consecutive integers
=Divisible by 3! = Divisible by 6
Hence proved.
He didn't solve it this way obviously because he wanted to show how to use strong induction...
@@riadsouissi yes , he wanted to motivate the use of strong induction
Excellent
18:28
13:16
I thought you wanted to prove TREE(3) > g64 using strong induction LOL.
Ex. 2: I put strong induction into your induction so you can use divisibility properties of consecutive integers as part of a proof involving strong induction while not using divisibility properties of consecutive integers as a proof itself.
(not against it btw, just looks fun)
for the second example, shouldn't it be "for k >= 1"?
wow amazing!!
thx
Hello
To be totally rigorous, a tree T=(V,E). So you’d be picking an edge e={u,v}\in E.
Sir can you give me the solution steps.please.
If x&y=xy/x+y then what is the value of (22&(23&(24&..........&(22020&22021)))))
x&y = xy/x+y = 2y (when x != 0)
So "x&" can to taken as the unary doubling operator. Your expression is 22021 with "x&" applied (22021-22 = 21999) times, so 22021 * 2^21999. Make rigorous via induction.
If, on the other hand, x&y = xy/(x+y), that gets interesting... Interesting enough to think that it might be a homework problem.
Sorry the question will be like that::::::::
If x&y=xy/(x+y) then what is the value of (22&(23&(24&..........&(22020&22021)))))
It's easy to prove every natural integer has a prime divisor with strong induction
where does f_(k+1)=f_(k+2)+f_k
here is the playlist for anyone asking
ruclips.net/p/PL22w63XsKjqykuLOimt7N59e6wn_aE0wd
Amazing as always! (i can't believe i'm third) :)
Hi pal, it is not my mind, but I think you could be a little more kind with your followers. I mean, give an answer or say hello. I know you are happy with maths.... you are brillant anyway. Thanks for all that knowledge.