Exercise 2.1: The Twelve Days of Christmas¶
The Twelve Days of Christmas is an 18th century English song traditionally sung during the Christmas holiday. In the song, the singer’s true love gives gifts each day. Here are the gifts on the first three days:
Day 1: A partridge in a pear tree.
Day 2: Two turtle doves and a partridge in a pear tree.
Day 3: Three French hens, two turtle doves, and a partridge in a pear tree.
The first day features one gift, the second three, and the third six. The fourth has ten, and so on. This extravagant giving continues for twelve days.
a) Write code to compute the total number of gifts given in the n days of Christmas. Do this using two for loops. Give your result for n = 12 and for n = 365.
b) It can be shown that
\begin{align} \sum_{i = 1}^m i = \frac{m(m+1)}{2}. \end{align}
Use this fact to do the calculation with a single for loop. If you feel like it, prove the above relation (not a coding but fun).
c) While we’re having non-coding fun, derive an expression for the total number of gifts given in n days of Christmas. (This is substantially harder than part (b) and you are not expected to do this; it’s just a fun challenge. As a hint, you may find it useful to consider the expansion of \((m - 1)^3\).)
Solution¶
a)
[1]:
n = 12
total_gifts = 0
for day in range(1, n+1):
for n_gifts in range(1, day+1):
total_gifts += n_gifts
print(total_gifts)
364
When we switch n to 365, we get 8,171,255 total gifts. Whew!
b) Day \(m\) features \(\sum_{i=1}^m i\) gifts. That is, day \(m\) features the sum of the first \(m\) integers gifts. This sum can be evaluated to be
\begin{align} \sum_{i = 1}^m i = \frac{m(m+1)}{2}. \end{align}
You can prove this by induction. The above relation is true for \(m = 1\). Assume it is true for \(m\). Let \(p = m + 1\). Then,
\begin{align} \sum_{i = 1}^p i = \sum_{i = 1}^{m+1} i = m+1 + \sum_{i = 1}^m i = m + 1+ \frac{m(m+1)}{2} = \frac{m^2 + 3m +2}{2} = \frac{(m+1)(m+2)}{2} = \frac{p(p+1)}{2}. \end{align}
It is thus proven.
We can use this result in our code.
[2]:
n = 12
total_gifts = 0
for day in range(1, n+1):
total_gifts += day * (day + 1) // 2
print("Total number of gifts:", total_gifts)
Total number of gifts: 364
Yep, same result!
c) We already established that day \(m\) features \(m(m+1)/2\) gifts. Then, the total number of gifts is
\begin{align} \sum_{m = 1}^n \frac{m(m+1)}{2} = \frac{1}{2}\left(\sum_{m = 1}^n m^2 + \sum_{m=1}^n m\right). \end{align}
We have already evaluated the second sum to be \(n(n+1)/2\). So, we are left to evaluate
\begin{align} \sum_{m = 1}^n m^2. \end{align}
A clever way of approaching this problem is to consider the expansion of \((m-1)^3\).
\begin{align} (m - 1)^3 = m^3 - 3m^2 + 3m - 1. \end{align}
We can rearrange this to get
\begin{align} m^3 - (m-1)^3 = 3m^2 - 3m + 1. \end{align}
Now, we will sum both sides to \(n\).
\begin{align} \sum_{m=1}^n \left(m^3 - (m-1)^3\right) &= \sum_{m=1}^n \left(3m^2 - 3m + 1\right) \\[1em] &= 3\sum_{m=1}^n m^2 - 3\sum_{m=1}^n m + n \\[1em] &= 3\sum_{m=1}^n m^2 - \frac{3n(n+1)}{2} + n \\[1em] &= 3\sum_{m=1}^n m^2 - \frac{3n^2 + n}{2}. \end{align}
We have again used our result that the sum of the first \(n\) integers is \(n(n+1)/2\). Now, consider the expression on the far left hand side. As that sum is evaluated, each term that is added cancels the term before it. This can be seen by writing it out.
\begin{align} \sum_{m=1}^n \left(m^3 - (m-1)^3\right) = (1 - 0) + (8 - 1) + (27 - 8) + (81 - 27) + \ldots. \end{align}
In the end, we are left the \(n^3\). So, we have
\begin{align} n^3 = 3\sum_{m=1}^n m^2 - \frac{3n^2 + n}{2}. \end{align}
Thus,
\begin{align} \sum_{m=1}^n m^2 = \frac{n^3}{3} + \frac{n^2}{2} + \frac{n}{6} = \frac{n(n+1)(2n+1)}{6}. \end{align}
So, the total number of gifts is
\begin{align} \sum_{m = 1}^n \frac{m(m+1)}{2} = \frac{1}{2}\left(\sum_{m = 1}^n m^2 + \sum_{m=1}^n m\right)= \frac{1}{2}\left(\frac{n(n+1)(2n+1)}{6} + \frac{n(n+1)}{2}\right) = \frac{n(n+1)(n+2)}{6}. \end{align}
Computing environment¶
[3]:
%load_ext watermark
%watermark -v -p jupyterlab
CPython 3.7.7
IPython 7.16.1
jupyterlab 2.1.5