1

In my proofs class, we're talking about strong induction and weak induction, and I don't really understand the difference. I get that for weak induction, we assume that an arbitrary $n = k$ is true, and then we set out to show that $n = k + 1$ is true. For strong induction, I know that we assume for all $j$, $1 < j < k + 1$, but I suppose I don't quite get what this means or how it changes a proof.

Could someone also help me adjust this proof I wrote or give me tips? It is supposed to prove using strong induction that we can always make change if the change is 54 cents or more using only 7 cent and 10 cent pieces. What I wrote seems like weak induction to me. Here's what I wrote:

We have that $7n + 10d = c$. For $c \geq 54$, it is claimed that it is always possible to make change. Let's think about this. $$7(2) + 10(4) = (54)$$ $$7(5) + 10(2) = (55)$$ $$7(8) + 10(0) = (56)$$ $$7(1) + 10(5) = (57)$$ $$7(4) + 10(3) = (58)$$ $$7(7) + 10(1) = (59)$$ $$7(0) + 10(6) = (60)$$ $$7(3) + 10(4) = (61)$$ $$7(6) + 10(2) = (62)$$ $$7(9) + 10(0) = (63)$$ $$7(2) + 10(5) = (64)$$ Note that from 54 to 64, there is a gap of 10. The same is true for 55 to 65, 56 to 66, and so on and so forth. So, if $c$ is true, so is $c + 10$. However, we've already established the truth of $c, c + 1, c + 2, ..., c + 9$, so then by induction, $c$ is true for $c \geq 54$.

Crimson
  • 31
  • 1
    That looks fine. Personally, I'd say that this somewhere between weak and strong induction. It's stronger than weak induction since you need to know that you can solve the problem for the $10$ preceding integers, not just the single preceding one. It's weaker than (typical) strong induction because the $10$ is bounded. You don't need to know that you can get all the values less than your target, just the prior $10$. Perfectly good argument though, – lulu Nov 18 '20 at 16:58
  • To me, strong induction is anything that requires more than 1 base case in the induction hypothesis step. E.g. proving binet's theorem. – Calvin Lin Nov 18 '20 at 18:34

0 Answers0