Newton's Little Formula

Newton’s Little Formula

NLF is a trick I first learned about in high school, although I learned it as “calculus of finite differences”. Maybe those two are the same thing, I’m not really up-to-date on the semantics.

Simply put, you have a sequence of numbers and you take differences between successive terms, and then differences between successive differences, and so on. If you eventually reach a constant row, you can easily read off a formula for the $n^{th}$ term of the sequence.

Quick Example

In A Formula of Newton by Eugene F. Krause¹, the following problem is given:

Problem Statement: Consider the sequence

$$5, 5, 7, 12, 24, 50, 100, 187, ...$$

What number follows 187 in the sequence?

Finite Differences Pyramid

First, list the sequence and its differences until we get to a constant row:

$$\begin{array}{lccccccccccccccc} \text{Term} & 5 & & 5 & & 7 & & 12 & & 24 & & 50 & & 100 & & 187 \\ \Delta^1 & & 0 & & 2 & & 5 & & 12 & & 26 & & 50 & & 87 & \\ \Delta^2 & & & 2 & & 3 & & 7 & & 14 & & 24 & & 37 & & \\ \Delta^3 & & & & 1 & & 4 & & 7 & & 10 & & 13 & & & \\ \Delta^4 & & & & & 3 & & 3 & & 3 & & 3 & & & & \\ \end{array}$$

Newton’s Little Formula

The general formula is:

$$f(n) = f(0) {n \choose 0} + \Delta^1 f(0) {n \choose 1} + \Delta^2 f(0) {n \choose 2} + \Delta^3 f(0) {n \choose 3} + \Delta^4 f(0) {n \choose 4}$$

So in this problem:

$$f(n) = 5 {n \choose 0} + 0 {n \choose 1} + 2 {n \choose 2} + 1 {n \choose 3} + 3 {n \choose 4}$$

Note that when using NLF, the first term in the sequence is the $0$th term. So the number after 187 would be the $8$th:

$$f(8) = 5 + 0 + 2 {8 \choose 2} + 1 {8 \choose 3} + 3 {8 \choose 4} = \boxed{327}$$

Unilluminating Examples

While showing this method to Curzon, I think he was quickly underwhelmed by its applications. As I was googling for problems involving NLF, the types of problems that came up were pretty dumb. Here’s a selection of what typically shows up on Google.

Dots in Diamonds

Given the following sequence of figures, find the number of dots in the $10$th figure:

Curzon immediately noticed it was $4n$. We then solved it with NLF for fun and made sure the answers matched, but I could tell it was pretty unsatisfying. OK, let’s find something harders.

Lines in Triangles

Same idea, but find the number of lines in the $10$th figure of the sequence below:

We started off on this problem by using NLF. Note there’s secretly a Figure 0 with only 1 dot and 0 lines. This trick allows us to get an extra term without counting the lines of a bigger triangle. It also conveniently makes the indexing of NLF align with the problem statement’s indexing. The difference pyramid looks like this:

$$\begin{array}{lccccccc} \text{Term} & 0 & & 3 & & 9 & & 18 \\ \Delta^1 & & 3 & & 6 & & 9 & \\ \Delta^2 & & & 3 & & 3 & & \\ \end{array}$$

You can see the second differences are constant, so the sequence is quadratic.

We apply Newton’s Little Formula:

$$f(n) = 0{n \choose 0} + 3{n \choose 1} + 3{n \choose 2} = 3n + 3{n \choose 2}$$

Finally:

$$f(10) = 3 \cdot 10 + 3 {10 \choose 2} = 3 \cdot 10 + 3 \cdot 45 = 30 + 135 = \boxed{165}.$$

Now I asked him to solve it without using NLF and he quickly noticed a way better solution. There are 3 sets of parallel line segments. Obviously there are the same number of segments in each set because of the symmetry of the problem, and each set is just a triangular number of lines.

So without doing any NLF nonsense, he came up with:

$$f(n) = 3{n+1 \choose 2}$$

I’ll admit at this point I was starting to feel like NLF was pretty unimpressive. It seemed like it was easier and more satisfying to solve these types of problems using intuitive counting methods.

Trickier Example

Determined to come up with a dot-counting or line-counting problem that would stump him without NLF, I went back to the drawing board and came up with this sequence of figures:

His first idea was to go back to an inductive idea and add $n$ entire hexagons (dodecagons?) at each successive figure and then correct for the double counting. This approach will work, but he kept making mistakes with the double counting. After a little while of struggling, I asked him to try it with NLF as I savored the sweet taste of victory.

As before, note that the $0$th figure will be a single dot. The difference pyramid looks like this:

$$\begin{array}{lccccccc} \text{Term} & 1 & & 12 & & 28 & & 49 \\ \Delta^1 & & 11 & & 16 & & 21 \\ \Delta^2 & & & 5 & & 5 \\ \end{array}$$

The second differences are constant 5’s, so it’s quadratic.

By Newton’s Little Formula:

$$f(n) = f(0){n \choose 0} + \Delta^1 f(0){n \choose 1} + \Delta^2 f(0){n \choose 2}.$$

From the pyramid:

• $f(0) = 1$
• $\Delta^1 f(0) = 11$
• $\Delta^2 f(0) = 5$

So the formula for the number of dots in the $n$th figure is:

$$f(n) = 1{n \choose 0} + 11{n \choose 1} + 5{n \choose 2} = \boxed{1+11n+5{n \choose 2}}.$$

Note that the form of this formula actually reveals a nice geometric counting argument where each term has a special meaning. Let’s colorize our diagram and formula to make each part easier to see:

$$f(n) = 1+11n+5{n \choose 2} = \color{#60A5FA}(12n - \color{#EF4444}(n-1) \color{#60A5FA}) + \color{#84CC16}5 {n \choose 2}$$

First note that the number of dots on the perimeter of the shape of the $n$th figure is $\color{#60A5FA}12n$. This can be seen by noting that there are $6n$ sides on the outside of the figure, which is the same as saying there are $n$ hexagons worth of sides. Since each hexagon is $12$ dots, there are $\color{#60A5FA}12n$ dots in total.

Next, we break down the interior of the shape into these clever “y-shapes” consisting of $\color{#84CC16}5$ dots each. There are clearly a triangular number, $\color{#84CC16}{n \choose 2}$, of these “y-shapes” in the interior. We’re almost there except you may have noticed that the “y-shapes” on the bottom actually double count a few of the perimeter points. How many perimeter points? Exactly $\color{#EF4444}n-1$. Combining these three types of points we arrive at the geometric interpretation of the formula derived from NLF. (Fun Fact: the NLF solution to most of these counting problems yield a geometric solution if you look carefully.)

I like this example because in a contest setting it’s possible to get caught up trying to figure out a clean way to break up this figure and avoid double counting. NLF, on the other hand, provided a fast, robotic, and repeatable method.

MATHCOUNTS 2013 Chapter Countdown Round

Here’s another example where NLF can actually be helpful:

Problem 73. What is the mean of the first five triangular numbers?

This is not an interesting problem, but if you replace $5$ with $100$ it becomes pretty annoying unless you’ve specifically studied this type of sum. Fortunately, NLF crushes this problem!

The nth triangular number is

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

The mean of the first n triangular numbers is:

$$M_n = \frac{1}{n} \sum_{k=1}^{n} T_k.$$

For $n = 1$ to $5$:

n	T_n	Partial Sum	Mean
1	1	1	1
2	3	4	2
3	6	10	10/3
4	10	20	5
5	15	35	7

Finite Differences Pyramid

$$\begin{array}{lccccccccc} \text{Term} & 1 & & 2 & & \frac{10}{3} & & 5 & & 7 \\ \Delta^1 & & 1 & & \frac{4}{3} & & \frac{5}{3} & & 2 & \\ \Delta^2 & & & \frac{1}{3} & & \frac{1}{3} & & \frac{1}{3} & & \\ \end{array}$$

So the mean sequence is quadratic in n. Note there’s nothing saying our differences have to be integers.

Plugging in to NLF:

$$f(n) = 1{n \choose 0} + 1{n \choose 1} + \frac{1}{3}{n \choose 2}$$

Plugging in $n = 99$ to find the sum of the first 100 triangular numbers:

$$f(99) = 1 + 99 + \frac{1}{6}(99)(98) = \boxed{1717}.$$

Closed Form

For completeness, let’s simplify our $f(n)$ into something easier. We’d also like to re-index it so that $n$ is 1-indexed instead of 0-indexed:

$$\begin{aligned} f(n-1) &= 1 + (n-1) + \frac{1}{3} \cdot \frac{(n-1)(n-2)}{2} \\[6pt] &= 1 + (n-1) + \frac{1}{6}(n-1)(n-2) \\[6pt] &= 1 + n - 1 + \frac{1}{6}(n-1)(n-2) \\[6pt] &= n + \frac{1}{6}(n-1)(n-2) \\[8pt] &= \frac{1}{6}(6n) + \frac{1}{6}(n-1)(n-2) \\[6pt] &= \frac{1}{6} \Big[ 6n + (n^2 - 3n + 2) \Big] \\[6pt] &= \frac{1}{6} (n^2 + 3n + 2) \\[6pt] &= \boxed{\frac{1}{6} (n+1)(n+2)}. \end{aligned}$$

Bonus Practice Problems

I’m not suggesting NLF is the best way to solve these, but it can be used to solve these :)

MATHCOUNTS 2005 School Team Round

Problem 9. In this $2$ by $2$ grid of squares, the total length of all $12$ of the line segments is $12$ units. In a similar $40$ by $40$ grid of squares that are the same size, what is the total length of all of the line segments?

MATHCOUNTS (Unknown Year/Round #1)

Problem ?. If the pattern continues as shown below, how many dots will be in stage 8?

MATHCOUNTS 2012-2013 School Handbook

Problem 261. This V-Dot pattern progresses as shown. As the pattern continues, how many dots will it take to make V-Dot $40$?

MATHCOUNTS 2000 School Team Round

Problem 5. The first four stellations are represented below. How many dots are in the 20th stellation?

MATHCOUNTS (Unknown Year/Round #2)

Problem ?. The first three hexagonal numbers are represented as follows:

Find the sum of the first five hexagonal numbers.

MATHCOUNTS 1996 Chapter Target Round

Problem 6. A pentagon train is made by attaching regular pentagons with one-inch sides so that each pentagon, except the two on the ends, is attached to exactly two other pentagons along sides as shown. How many inches are in the perimeter of a pentagon train made from 85 pentagons?

MATHCOUNTS 2004-2005 Workouts

Workout 8, Problem 5. If this pattern of cubes is continued, how many cubes will be in the $20^{\text{th}}$ formation?

Footnotes

1. Eugene F. Krause, A Formula of Newton. Department of Mathematics, The University of Michigan, Ann Arbor, Michigan 48104. ↩