A popular winter Math problem is the counting of presents given during the 12 days of Christmas.
On the 1st day of Christmas my true love gave to me a partridge in a pear tree.
On the 2nd day of Christmas my true love gave to me 2 turtle doves, and a partridge in a pear tree.
On the 3rd day of Christmas my true love gave to me 3 french hens, 2 turtle doves, and a partridge in a pear tree.
... and so on through day 12.
The problem is to count the number of presents received during the 12 days, and for the truly masochistic, the cost of the twelve day's worth of presents in today's dollars.
I love this type of problem because it's an algebra problem and it involves sums of series, two favorite subjects of mine.
The problem is to compute this sum:
One nice approach to doing the computation is here. But, what I don't like about this approach is that it doesn't quite connect the dots about how you can use Pascal's triangle to solve this problem for the general case. So, I came up with my own approach.
The first part of my approach is to determine what 1+2+3+...+n is, for each of the 12 lines of numbers we want to add up. It turns out that 1+2+3+...+n = n(n+1)/2. But, don't take my word for it. You can see it for yourself with Gauss' approach:
If the sum of the first n consecutive integers is S then:
But, you can reverse the terms in the series and get the same sum:
Add up the two series:
2S = (1+n)+(2+n-1)+(3+n-2)+...+(n+1)
There are n terms in 2S, and each term adds up to n+1, so:
2S = n(n+1), or:
So, the 1st sum we need to compute is 1, or 1(2)/2 by the formula we just derived.
The 2nd sum is 1+2, which is 2(3)/2 by the formula.
The 3rd sum is 1+2+3, or 3(4)/2.
The 4th sum is 1+2+3+4, or 4(5)/2, and so on.
Now, let's look at the sum of the 12 sums, calling it B for big sum:
B = 1(2)/2 + 2(3)/2 + 3(4)/2 + 4(5)/2 + ... + 12(13)/2 by applying the formula we derived for the sum of each row.
Then, 2B = 1(2) + 2(3) + 3(4) + 4(5) + 5(6) + ... + 12(13)
But, 2B = 1(1+1) + 2(2+1) + 3(3+1) + 4(4+1) + 5(5+1) + ... + 12(12+1)
We can rewrite 2B as 1^2 + 1 + 2^2 +2 + 3^2 + 3 + 4^2+4 + 5^2 + 5 + ... + 12^12 + 12
Now, rearrange the terms in 2B and we get:
2B = (1^2 + 2^2 + 3^2 + 4^2 + 5^2 + ... + 12^2) + (1 + 2 + 3 + 4 + 5 + ... + 12)
Well, we're closer to our answer, really, but we still have some work to do.
We can use our formula again for the sum of the first n consecutive integers and determine that:
1 + 2 + 3 + 4 + 5 + 6 ... + 12 = 12(13)/2 = 78
But, now we have to determine the sum of the squares of the first 12 positive integers.
The formula for the sum of the squares of the first n consecutive integers is this:
But, I hear you asking where this formula came from. This is not very intuitive. I agree and I'm all about intuitive. So, I found this nice visual "proof" of this formula here. It's not a proof at all but it illustrates very visually how you can compute the sum of the first n squares.
Now, back to our big sum:
2B = the sum of the first 12 squares plus the sum of the first 12 integers, or if we replace each sum with its corresponding formula:
2B = 12(13)(25)/6 + 12(13)/2 = 650 + 78 = 728.
So, B = 728/2 = 364
That's almost one present for every day of the year!
As a final exercise, let's generalize the formula for any number of days, n.
2B = the sum of the first n squares plus the sum of the first n integers.
2B = n(n+1)(2n+1)/6 + n(n+1)/2
We multiply the second part of the sum by 3/3:
2B = n(n+1)(2n+1)/6 + 3n(n+1)/6, or:
2B = [n(n+1)(2n+1) + 3n(n+1)] / 6, or:
B = [n(n+1)(2n+1) + 3n(n+1)] / 12. Factor out n(n+1) from both sides and we get:
B = n(n+1)[(2n+1) +3] / 12 = [n(n+1)(2n+4)]/12
So, now you're ready. If someone asks you how many presents you'd get if there were 24 days of Christmas you'd compute, hopefully using mental Math tricks, (24)(25)(52)/12 = (2)(25)(52) =(50)(52) = 2600.
If you want to do a little more exploration convince yourself that this formula we just derived for counting presents is algebraically equivalent to the element in Pascal's triangle illustrated in the article I referenced earlier. To do this you will need to know that there's a correspondence between entries in Pascal's triangle and binomial coefficients and how to compute binomial coefficients. You can read more about this connection here.
Merry Christmas, everyone!