I had a quick look through the problem set and since the topic was induction I thought it would be fun to think through how you'd do all of the problems directly (without induction).
The most fun one I think is how you compute 1^2 + 2^2 + ... + n^2 without induction.
I've seen the answer and inductive arguments lots of times but have never thought about or seen how you do it directly, and so I think I've rediscovered the combinatorial way to do it.
---
We want to compute 1^2 + 2^2 + ... + n^2.
What does each term k^2 count? Fix a number k. We can think of k^2 as the number of ways to choose an ordered pair (a, b) where each of a, b is an integer from {1, 2, ..., k}.
This means the whole sum counts the number of triples (k, a, b) where 1 <= a, b <= k <= n. Now we build all such triples in a different way.
The trick is to work inside the set {1, 2, ..., n+1}, and let k+1 always be the largest number we pick. That way, anything else we pick is automatically at most k, so it’s a valid choice for a and b.
We split into two cases:
1. Triples with a != b: Choose 3 distinct numbers from {1, ..., n+1}. Call them x < y < z. Let k = z − 1. Then (a, b) can be (x, y) or (y, x). Both choices have a, b <= k, so both give valid triples (k, a, b). So each 3-element subset gives 2 different triples with a != b.
2. Triples with a = b: Choose 2 distinct numbers from {1, ..., n+1}. Call them y < z. Set k = z - 1 as before, and a = b = y. Then we get a valid triple, and so each 2-element subset gives exactly 1 such triple.
These two processes produce all triples (k, a, b) with 1 <= a, b <= k <= n, and nothing is missed or double-counted So we can count them:
There are C(n+1, 3) ways to choose 3 distinct numbers; each gives 2 triples.
There are C(n+1, 2) ways to choose 2 distinct numbers; each gives 1 triple.
Sick. Thank you very much for posting this. Combinatorial arguments always feel a bit like wizardry to me, I never got the handle of them - where did you get the trick of working in the set {1, ..., n+1}?
You'll know the sum 1+2+...+n is a triangular number, and a triangle of dots is half a rectangle, and the relevant rectangle is n by n+1, so the sum is n(n+1)/2.
For the sum of squares, it's psychologically easier to use blocks: Stack them up inside a box with a base of dimensions n*(n+1). Start with an n*n square base layer with (n-1)*(n-1) on top, etc, forming some sort of pyramidal shape in one corner of the box.
Take two more copies of that stack, rotate them appropriately and put them in the box. All going well, if you take a copy of those three stacks and turn it upside down, it will slot in nicely and give you a stack of exactly n*(n+1)(2n+1).
Not rigorous at all, but one should be able to make it so (just as for the triangle-rectangle, one notices that the sum is (1+n + 2+n-1 + ...)/2).
I had a quick look through the problem set and since the topic was induction I thought it would be fun to think through how you'd do all of the problems directly (without induction).
The most fun one I think is how you compute 1^2 + 2^2 + ... + n^2 without induction.
I've seen the answer and inductive arguments lots of times but have never thought about or seen how you do it directly, and so I think I've rediscovered the combinatorial way to do it.
---
We want to compute 1^2 + 2^2 + ... + n^2.
What does each term k^2 count? Fix a number k. We can think of k^2 as the number of ways to choose an ordered pair (a, b) where each of a, b is an integer from {1, 2, ..., k}.
This means the whole sum counts the number of triples (k, a, b) where 1 <= a, b <= k <= n. Now we build all such triples in a different way.
The trick is to work inside the set {1, 2, ..., n+1}, and let k+1 always be the largest number we pick. That way, anything else we pick is automatically at most k, so it’s a valid choice for a and b.
We split into two cases:
1. Triples with a != b: Choose 3 distinct numbers from {1, ..., n+1}. Call them x < y < z. Let k = z − 1. Then (a, b) can be (x, y) or (y, x). Both choices have a, b <= k, so both give valid triples (k, a, b). So each 3-element subset gives 2 different triples with a != b.
2. Triples with a = b: Choose 2 distinct numbers from {1, ..., n+1}. Call them y < z. Set k = z - 1 as before, and a = b = y. Then we get a valid triple, and so each 2-element subset gives exactly 1 such triple.
These two processes produce all triples (k, a, b) with 1 <= a, b <= k <= n, and nothing is missed or double-counted So we can count them:
There are C(n+1, 3) ways to choose 3 distinct numbers; each gives 2 triples.
There are C(n+1, 2) ways to choose 2 distinct numbers; each gives 1 triple.
Therefore,
1^2 + 2^2 + ... + n^2
= 2 * C(n+1, 3) + C(n+1, 2)
= 2 * [(n+1)n(n-1)/6] + [(n+1)n/2]
= (n+1)n(2n+1)/6.
Sick. Thank you very much for posting this. Combinatorial arguments always feel a bit like wizardry to me, I never got the handle of them - where did you get the trick of working in the set {1, ..., n+1}?
You'll know the sum 1+2+...+n is a triangular number, and a triangle of dots is half a rectangle, and the relevant rectangle is n by n+1, so the sum is n(n+1)/2.
For the sum of squares, it's psychologically easier to use blocks: Stack them up inside a box with a base of dimensions n*(n+1). Start with an n*n square base layer with (n-1)*(n-1) on top, etc, forming some sort of pyramidal shape in one corner of the box.
Take two more copies of that stack, rotate them appropriately and put them in the box. All going well, if you take a copy of those three stacks and turn it upside down, it will slot in nicely and give you a stack of exactly n*(n+1)(2n+1).
Not rigorous at all, but one should be able to make it so (just as for the triangle-rectangle, one notices that the sum is (1+n + 2+n-1 + ...)/2).