The Odd Pyramid

Programming challenges during job interviews are discouraged nowadays, as it gives a skewed image of the skills of the respective candidate.

But I really liked to give a candidate this particular programming challenge, as it showed me how the developer thought about problems before he started coding. For thinking of how the solutions look like before starting to code saves a lot of time in this case.

Task

The odd numbers are aligned as follows to a triangle of infinite height:

In the first row there’s the first odd number, 1. In the second row the next two odd numbers, so 3 and 5. In the third the next three, and so on.

Write a program that provides the sum of all the numbers in the row with the number i.

Solution

I really like this task. It appears to be very complicated and complex to calculate, until you sum the first couple of lines manually.

That would look like this:

For the row with the number $i$ the solution appears to be $i^3$ - a program calculating this is trivial. Here’s a solution in Python that also returns a table with the first 10 lines:

 1def solution(i):
 2         return i ** 3
 3
 4def nth_odd(n):
 5         return 2 * n - 1
 6
 7def sum_i(i):
 8         return i * (i + 1) // 2
 9
10def gen_line(i):
11         k = sum_i(i - 1) + 1
12         return [nth_odd(k + j) for j in range(i)]
13
14def gen_line_str(i):
15         return " ".join(map(str, gen_line(i)))
16
17return [["*Row*", "*Numbers*", "*Result*"], None] + [[i,gen_line_str(i), solution(i)] for i in range(1, 11)]

This code also contains methods to generate the table, something that the task actually doesn’t ask for. But that is usually the biggest headscratcher for a prospective candidate until you give him the hint that the solution may be way easier than he thinks and he should just have a look at what the numbers look like.

I do not expect people to be able to prove that this is the case, even though the method to construct the pyramid is actually the key to understanding why i^3 is the correct solution.

But for that we need some number theory.

Proof

First we need a formula for the sum of all natural numbers up until and including a number $n$. That formula has been found by the German mathematician Gauß: $\frac{n(n+1)}{2}$ - let’s prove that this is the case:

Lemma Gauß

For the function $S : \mathbb{N} \rightarrow \mathbb{N}$ defined as

$$S(n) := \sum_{i=1}^n = 1 + \ldots + n$$

we want to prove: $S(n) = \frac{n \cdot (n + 1)}{2}$

Proof by induction

• Anchor

  For $n = 1$ : $$S(1) = \sum_{i=1}^1 = 1 = \frac{1 \cdot 2}{2}$$

  which was to be shown.

• Assumption

  Let’s assume, the property holds for all numbers up to $n - 1$.

• Step

  Then:

  $$S(n) = n + S(n - 1) = n + \frac{(n - 1) \cdot ((n - 1) + 1)}{2}$$

  $$= \frac{2n + n \cdot (n - 1)}{2}$$

  $$= \frac{2n + n^2 - n}{2}$$

  $$= \frac{n + n^2}{2}$$

  $$= \frac{n \cdot (n + 1)}{2}$$

  which was to be proven.

Lemma Sum of the first n odd numbers

Here’s a surprising fact: the sum of the first $n$ odd numbers is always $n^2$ - meaning, all square numbers can be formed through the sums of the odd numbers:

Es gibt den folgenden überraschenden Zusammenhang: die Summe der ersten $n$ ungeraden Zahlen ist immer $n^2$ - sprich, alle Quadratzahlen lassen sich als Summe der ungeraden Zahlen abbilden:

Proof by induction

• To prove

  Given the function $T : \mathbb{N} \rightarrow \mathbb{N}$ defined as:

  $$T(n) := \sum_{i=1}^n 2i - 1 = 1 + 3 + 5 + \ldots + 2n - 1$$

  meaning the sum of the first $n$ odd numbers. We want to show that $T(n) = n^2$.

• Anchor

  For $n = 1$ we have:

  $$T(1) = \sum_{i=1}^1 (2i - 1) = 2 - 1 = 1$$

  and therefore also $T(1) = 1^2$.

• Assumption

  Let’s assume, the property is true for all numbers up to $n - 1$.

• Step

  As

  $$T(n) = 2n - 1 + T(n-1)$$

  this holds:

  $$T(n) = 2n - 1 + (n - 1)^2$$

  $$= n^2 - 2n + 1 + 2n - 1$$

  $$= n^2$$

  which was to be proven.

Proof of the solution

Note that the sum of all numbers in row i is equal to the sum of all numbers including row i minus the sum of all numbers up to row i - 1.

The number of odd numbers up until and including row i is exactly the sum of all odd numbers up to the sum of all natural numbers up to i. For our problem that means:

$$P(i) = T(S(i)) - T(S(i - 1)) = S(i)^2 - S(i-1)^2$$

After substituting $S$ we have:

$$P(i) = \frac{i² \cdot (i + 1)²}{4} - \frac{i² \cdot (i - 1)²}{4}$$

$$= \frac{i² \cdot ((i² + 2i + 1) - (i² - 2i + 1))}{4}$$

$$= \frac{i² \cdot 4 \cdot i}{4}$$

$$= i³$$

which proves that our solution is correct.