Discussion about this post

User's avatar
Adam Kelly's avatar

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.

Expand full comment
2 more comments...

No posts

Ready for more?