  ## An Odd Question About Pascal's Triangle

How many odd numbers are there on the $2013^{th}$ row of Pascal's Triangle? Is there a general way to find out how many are on the $n^{th}$ row?

We start by asking some good questions, contextualizing them for the investigation at hand, as appropriate...

Have I named everything that might be significant? (i.e., the number of odd values on the $n^{th}$ row of Pascal's Triangle)

Let's denote the number of odd values on the $n^{th}$ row by $f(n)$.

What do the smallest several cases tell me? Is there a pattern? we need to look at the first few rows of Pascal's triangle

Inspecting Pascal's triangle, we find $f(n)$ for the first several values of $n$ (calling the top row $n=0$):

 $n$ $f$ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 2 4 2 4 4 8 2 4 4 8 4 8 8 16 2

Is there a recursive relationship? Is there is a way to predict $f(n)$ values farther to the right in our list from those $f(n)$ values that occur earlier.

Making the following breaks in the sequence of $f(n)$ values, we notice a pattern: Each block can be obtained by doubling all of the $f(n)$ values seen prior to that block

$$1 \ \vert \ 2 \ \vert \ 2, 4 \ \vert \ 2, 4, 4, 8 \ \vert \ 2, 4, 4, 8, 4, 8, 8, 16 \ \vert \ 2, 4, 4, 8, 4, \dots$$

Where does the behavior change? Here, the behavior changes at the breaks between blocks of numbers

Notice, the breaks between the blocks above occur just after the $1^{st}$, $2^{nd}$, $4^{th}$, $8^{th}$, and $16^{th}$ positions.

Since each of these blocks (with the exception of the first one) begins with a $2$, we conjecture that for any positive integer $m>1$, row $2^m$ contains only even numbers, except for the two $1$'s on the ends of the row.

Can we prove this conjecture? ...perhaps by induction? We would need to show that it holds for the first row of Pascal's triangle, and that if it holds for row $2^k$, then it also holds for row $2^{k+1}$...

The list above shows that the result holds for the first few values of $m$, so the basis step of an argument by induction is already established.

It remains to show that if our conjecture is true for row $2^k$, then it must also be true for row $2^{k+1}$.

Suppose the line from A to C in the diagram below represents row $2^k$, with its two odd values colored blue and the even numbers shown in red. Similarly, the line from B to D represents row $2^{k+1}$. Note first that -- in this problem -- the values of the numbers in Pascal's triangle are not near as important as their parity (i.e., whether they are even or odd). In particular, any triangular arrangement of numbers that has a single odd number at the top, and odd numbers down the two sides will behave in exactly the same way. The numbers of odd values on each row will agree with those for Pascal's triangle, and the odd values themselves will appear in the same locations.

Next, note that since the sum of two even numbers is even, the inductive hypothesis requires the triangular array of numbers shown in red must all be even. Consequently, the line of values from A to X (but not including X) and C to X (again, not including X) must contain only odd numbers. By our earlier observation about parity, this requires the same pattern of odds and evens exist in $\triangle ABX$ and $\triangle CXD$ as $\triangle OAC$, with the exception of what happens at X. Since the two values directly above X are both odd, we know X must instead be an even value. So, row $2^{k+1}$ consists of only even numbers as well, again with the exception of the two $1$'s on the ends of that row. Hence, by the principle of mathematical induction, it must be true that for all positive integers $m>1$, row $2^m$ contains only even numbers, except for the two $1$'s on the ends of the row.

Can I "chip away" at the problem? Can I write this problem in terms of a simpler one? Here, since we are trying to find $f(n)$ for a given $n$, perhaps we can express it in terms of a single previous $f(n)$ value. (This would really just a refinement of our previous search for a recursive relationship.)

The "doubling" of the pattern of odds and evens seen in the green cells when comparing rows between row $2^k$ and row $2^{k+1}$ versus those between row $0$ and $2^k$ is something we can exploit. Let us color all of the odds on the first few rows of Pascal's triangle to get a better feel for how this happens: Seeing the triangular patterns above, suggests the following way way to define and compute $f(n)$, the number of odd values on the $n^{th}$ row of Pascal's triangle:

1. $f(0) = 1$
2. If $n = 2^m$ for some integer $m$, then $f(n) = 2$
3. If $n = 2^m + r$ where $r$ is an integer and $2^m$ is the highest integer power of $2$ less than $n$. Then $f(n) = 2 \cdot f(r)$.

To show how we might then use this definition to compute $f(n)$ for any $n$, let us consider two examples.

First, we find $f(14)$ (note, we can verify the calculation by simply counting the blue numbers in the 14th row in the graphic above):

$$\begin{array}{rcl} f(14) &=& f(2^3 + 6) &=& 2 \cdot f(6)\\ &=& 2 \cdot f(2^2 + 2) &=& 2^2 \cdot f(2)\\ &=& 2^2 \cdot 2 &=& 8 \end{array}$$

Now, we give an example of it in use to compute $f(n)$ for a larger value of $n$:

$$\begin{array}{rcl} f(2013) &=& f(2^{10} + 989) &=& 2 \cdot f(989)\\ &=& 2 \cdot f(2^9 + 477) &=& 2^2 \cdot f(477)\\ &=& 2^2 \cdot f(2^8 + 221) &=& 2^3 \cdot f(221)\\ &=& 2^3 \cdot f(2^7 + 93) &=& 2^4 \cdot f(93)\\ &=& 2^4 \cdot f(2^6 + 29) &=& 2^5 \cdot f(29)\\ &=& 2^5 \cdot f(2^4 + 13) &=& 2^6 \cdot f(13)\\ &=& 2^6 \cdot f(2^3 + 5) &=& 2^7 \cdot f(5)\\ &=& 2^7 \cdot f(2^2 + 1) &=& 2^8 \cdot f(1)\\ &=& 2^8 \cdot 2 &=& 512 \end{array}$$