A few days back, I set a maths challenge:
Prove that, for arbitrarily large N, the total number of gifts given up to and including day N is
( N (N+1) (N+2) ) / 6
I hope you enjoyed it. It's time for a solution:
Lemma: Number of gifts on Day N
First, we need a lemma. (In mathematics, a lemma is a something we prove as a stepping stone towards our main result).
Before we can work out the number of gifts given up to and including day n, we need to work out the number of gifts given on day n. We shall prove that this is ( n ( n+1 ) ) / 2. First, we shall show this in a way that's easy to see what's going on. Then we'll actually prove it, more rigorously.
On day N, the number of gifts given is 1 + 2 + 3 + … + (n-1) + n.
We can write that same expression backwards: n + (n-1) + … + 2 + 1.
What we then do is add up those two expressions (the one written forwards, and the one written backwards) — we can add the corresponding pairs of numbers, thus:
1 + 2 + 3 + … + n
| | | |
n + (n-1) + (n-2) + … + 1
Each pair of numbers adds up to n+1. So, adding up the whole equation we get:
(n+1) + (n+1) + (n+1) + … + (n+1)
= n(n+1)
But this was what we got when we added up twice what we needed. So the number of gifts given on day n is half this:
n ( n+1 ) / 2
Proof by Induction
Argued like that, it was easy to see what was going on. We could do with proving it a little more rigorously, and for that we will use proof by induction.
Proof by induction is a technique for proving something to be true for any positive integer. You show two things:
(i) the statement you are trying to prove is true when N = 1.
(ii) if you know that the statement you're trying to prove is true for N = n, then it follows it is also true for n+1.
It then follows that it's true for 1, and hence for 2, and hence for 3, and so on up to any number you wished. The puzzle we're solving said we may assume this to be a valid and logical technique for solving problems like this
Lemma Revisited: Number of gifts on Day N
So, we're trying to show that on day N, the number of gifts given was ½ N ( N+1 )
First, we show this works for N = 1. On day 1, ½ N ( N+1 ) evaluates to ½ · 1 · 2 = 1. Sure enough, on day 1 a single gift was given (a partridge in a pair tree).
Then, we assume we know that this works for N = n. On day n + 1, all the gifts of the previous day were given again, and an additional n + 1 gifts were given. So the number of gifts given was:
½ n ( n+1 ) + (n + 1)
= ( n + 1 )( ½n + 1 )
= ½ ( n + 1 )( n + 2 )
= ½ ( n + 1 )( ( n + 1 ) + 1 )
…which is our expression when N = n + 1. ||
Now gifts up to and including day 1
So now we try to prove our main proposition, that the number of gifts up to and including day N is ( N (N+1) (N+2) ) / 6
We'll do it by induction again. Now that we've practised this technique on an easier example, this shouldn't be difficult - we just do the same again, being careful because we're dealing with a cubic expression.
Start with day 1: ( N (N+1) (N+2) ) / 6 is ⅙ ( 1 · 2 · 3 ), which is 1. Again, this is what we were hoping for - up to and including day 1, only a single partridge had been given
Gifts up to and including day n+1
Now let's assume we know our proposition to be true on day n. What happens on day (n+1)?
The answer is that all the gifts up to and including day n are given. And then, in addition, the number of gifts given on day (n+1) are given. We know the number of gifts up to and including day n, because we're assuming that by using induction. We know the number of gifts on day (n+1) from our lemma. It's just a matter of adding them up.
So, the number of gifts up to and including day (n+1) is as follows:
[ ⅙ n ( n + 1 ) ( n + 2 ) ] + [ ½ ( n + 1 ) ( n + 2 ) ]
We can factor out both (n+1) and (n+2):
= ( n + 1 ) ( n + 2 ) ( ⅙ n + ½ )
Lastly, we factor out the one-sixth:
= ⅙ ( n + 1 ) ( n + 2 ) ( n + 3 )
= ⅙ ( n + 1 ) ( ( n + 1 ) + 1 ) ( ( n + 1 ) + 2 )
… which is what we were looking for. ||
40 days of Easter
That means we can solve another puzzle which you'd (probably) never have had the patience to add up by hand.
Imagine if, instead of the 12 days of Christmas, someone wrote a song entitled The 40 Days of Easter. I estimate it would take about 25 minutes to sing, which is one reason why this would never catch on in the same way. But how many gifts would be given in total?
Easy.
⅙ · 40 · 41 · 42
= ⅙ ( 68,880 )
= 11,480 gifts
So now you know.
Add new comment