#Induction
vestal heronBOT
frigid ermine
Understanding Proof by Strong Induction
ornate elbow
are you asking why induction works in general or specifically why strong induction works
willow anvil
the key is that there's a base case
say you've proven something for n=1
and then you do your induction by considering hypothesis to be true for n=i yada yada
the reason it works is because you've already know the n=1 case is true
so once induction is done you also know that n=2 case works
since n=2 works, then n=3 works too
and so on
ornate elbow
minus 5 because you have a 5 cent "unit" to work with. that is, if k-5 is doable, then with just another 5 cents, k is also doable. this is how the proof was constructed
ornate elbow
just so it's clear, the 'usual' induction is to assume hypothesis true for k (or <= k in strong induction), then prove true for k+1. here the book uses the equivalent, which is assume hypothesis true for all <= k-1, then prove true for k. (the only adjustment needed is what the bound for k is, but that's besides the point) -- this is just done for easier demonstration
first it was proven that 20 is possible (base case).
now, we assume the inductive hypothesis "for any k > 20, there is a valid combination for k-1" and proceed to prove that there is also a valid combination for k.
we have a problem. we know that if, say, we showed a valid combination for 20, then we can keep adding 5 cents into 25, 30, 35, etc. creating an infinite list of numbers with valid combinations. similarly, if we showed a valid combination for 21, then we have it for 26, 31, 36, etc... BUT we cannot prove it in this "infinite list" way for 21,22,23,24. so we can "treat" them as base cases and actually show explicit combinations for them
if k is 21, 22, 23, or 24: then we give an explicit combination. (the book lists them)
if k is 25: then we consider that 20 + 5 could produce this
if k is 26: then we consider that 21 (itself a valid combination) + 5 could produce this
etc... if you work out the pattern, you will see that for any k >= 25, if you subtract 5 (this being k-5), it will for sure be a known valid combination. adding the 5 back pulls you back to k, but you know (intuitively, and from the preliminary testing above!) that adding 5 will always be a valid combination. thus, generally...
if k >= 25: then note that k-5 is in [20, k-1], which means that k-5 satisfies the inductive hypothesis, and therefore has a valid combination. but adding 5 to any valid combination produces a valid combination as well. thus, k-5 + 5 = k has a valid combination.
sorry if i took long typing i was figuring out the best way to explain it, while eating dinner lol
the remark at the end is also quite delightful, with regards to 21-24 being "base cases": in fact there is no need to consider them as base cases, because they were proven after the assumption of the inductive hypothesis. just that we think of them as base cases because we did not use the inductive hypothesis AT ALL (after assuming it), k=21,22,23,24 in the proof have valid combinations regardless.
ornate elbow
because the problem was about making combinations using just 5- or 6-cent units. in fact, using 6 instead of 5 would have proved it in much the same way; the only difference is that you would need to consider the extra "base" case of 25. i think you will understand the entire thing if you figure out why 6 works as well
you can try the perspective of approaching the problem for the first time (you do not need to think of induction for now): it would be immediately obvious that 5 or 6 satisfy the condition, but you can't use N=5 because obviously 7 doesn't satisfy. so how do you find a correct N?
it shouldn't take long to notice that if you just keep adding 5 to 5, you will get 5,10,15,20,... which are all numbers that satisfy the condition. also, if you keep adding 5 to 6, you will get 6,11,16,21,... which are also all satisfying the condition.
now, if only 7, 8, and 9 satisfy, then you could have covered every single number greater than 5
5,10,15,20,...
6,11,16,21,...
7,12,17,22,...
8,13,18,23,...
9,14,19,24,...
the only problem is: 7, 8, and 9 do not satisfy the condition.
but you see the pattern here: if you can find 5 consecutive numbers, let's just say n, n+1, ..., n+4 that satisfy, then you can keep adding 5 to them and this will surely cover the entirety of the numbers which are greater than or equal to n. this strategy narrows your search. the easiest way, intuitively, is to generate:
5+5+5+5
5+5+5+6
5+5+6+6
5+6+6+6
6+6+6+6
(understand why this works!)
this corresponds to 20,21,...,24.
IN FACT you can prove that 20 is the smallest N that solves the problem, because you can exhaust that 19 does not satisfy the condition
ps. i was typing this before you asked the follow up question but i think this answers it
you could have gotten a correct N from something like
- 5 + 5 + 5 + 5 + 5
- 5 + 5 + 5 + 5 + 6
- 5 + 5 + 5 + 6 + 6
- 5 + 5 + 6 + 6 + 6
- 5 + 6 + 6 + 6 + 6
as well, but i introduced the tightest case where you wouldn't have any 5's left to "transform" into 6's after you obtain the 5 numbers you needed
the problem wasn't asking for the smallest N after all
this kind of boils down to intuition honestly
ornate elbow
perhaps, yes... it's not exactly the same but it reminds me of a "stars and bars" kind of problem
additionally, here, if you have a proposed value of N, in our case 20, all you needed to check is that the next lower number 19 does not have a combination.
it is not immediately obvious but i think this is the most elegant way to show:
for nonnegative integer pairs (m, n), if m+n >= 4, the smallest that 5m + 6n could possibly be is 20. if m+n <= 3, the largest that 5m + 6n could possibly be is 18. therefore, it should be evident that 19 cannot be formed from a valid combination.
ornate elbow
the assumption is essential for induction
vestal heronBOT
Understanding Proof by Induction