Proving Binomial Theorem using Mathematical Induction

The Binomial Theorem is the perfect example to show how different streams in mathematics are connected to one another: its coefficients have combinatorial roots and can be traced to terms in Pascal’s Triangle, and expansion of binomials to different orders of power can describe probability and combination distributions. The combinatorial proof as under requires no need for proving again, but after learning a method called Mathematical Induction from incessant internet browsing on a late Saturday night, I thought, why not give it a shot?

Mathematical Induction is a method of mathematical proof used to prove an expression true for all natural numbers. The steps are as under:

  1. State the proposition P(n) that needs proving.
  2. The Basis: Show P(n) is true, when n=1.
  3. The Inductive Step:
    1. Assume n=k
    2. If P(k) is true, show that P(k+1) is true
  4. If P(k+1) is true, therefore P(n) is true.

Binomial Theorem Proof w. steps 3 - Copy

(Side-note: It’s not everyday you get to use Q.E.D.)


The Game of Permutations

What do mathematicians do? Simply, they try to find a mathematical model that describes the patterns that emerge in life, the universe, and everything. Mathematicians are employed in numerous industries in everything from manufacturing to finance. Mathematicians also, however, research in other topics that appear to have very little mathematical foundation. Take for example, board games. Sudoku are some examples that have been under the scrutiny of mathematicians all over the world.

The quest to accurately find all the possible Sudoku structures has been going on for many decades, and can often require the use of super computers to deal with the complex calculations involved. While it may appear, at first, to involve simple permutation calculations, the rules of the game restrict certain permutations from being included. A variety of research has been conducted to solve these problems, and I will try to do my best to explain them as easily as possible.

The research paper credited to have accurately calculated all the possible Sudoku arrangements goes Professor Bertram Felgenhauer (Dresden University of Technology, Germany) and Professor Frazer Jarvis’ (University of Sheffield, UK) paper Enumerating Possible Sudoku Grids (2005).

If we were to look at all the possible permutations for a 9 x 9 Sudoku grid exempt of its rules, it would total up to 9!^9 = 1.0911069e+50 (9! for each of the nine 3 x 3 grids).  Their final calculation amounted to 6670903752021072936960 ≈ 6.671 × 1021.

The process in which they have calculated the answer is simplified as follows:

We shall create a classification system to identify parts of the grid.

  • The 9 x 9 Sudoku grid is called a grid
  • each 3 x 3 grid will be called a block. Therefore there are 9 blocks in total, creating the 9 x 9 grid.
  • the three rows of blocks will be called bands of the grid.
  • the three columns of blocks will be called the stacks.
  • A cell in the ith row and jth column is said to be in (i,j) position.
  • The number of distinct Sudoku grids will be denoted N.
  • The digits 1-9 that fill up each block will be referred to as symbols or digits.

Fig 1

Fig. 1: Each block is denoted a name as B#.

How many ways are there to fill B1 in a valid way? (Remember that each block must contain nine symbols of 1 to 9 with no repetitions)

Looking solely at B1, we know that the first cell (1,1) has nine possible options (i.e., 1, 2, 3, 4, 5, 6, 7, 8, 9). The second cell (1,2) now has eight possible options, since the digit used in the (1,1) cannot be repeated. The third cell (1,3) now has seven remaining possible options and so onWhat we are essentially doing is counting the number of valid of permutations of nine symbols for B1: how we could arrange 9 symbols into 9 cells/order 9 symbols. Therefore the total permutations for B1 are 9P9 = 9!. However, we need to calculate the number of valid arrangements, since B1 will depend on the arrangements of other blocks.

Fig 2 Fig. 2: One possible permutation for B1.

If N represents the number of distinct grids (abiding by game rules) and Nthe number of distinct grids with the B1 permutation shown in Fig. 2, the total number of valid grids will be N1×9!, so N1=N/9!.

The authors decide to permute B2 and B3 in terms of one permutation of B1 as shown in Fig. 2.

Since 1, 2, and 3 occur in the first row in B1, these numbers cannot occur in the rest of the row. So only the numbers 4, 5, 6, 7, 8, and 9 from the second and third rows of B1 can be used in the first row in B2 and B3.

They classify these two possibilities as pure top rows – when the numbers {4,5,6} as in the second row of B1 are kept together in B2 and the numbers {7,8,9} as in the third row of B1 are kept together in B3, and the swapped version of this – and the rest of the possibilities as mixed top rows – where the sets {4,5,6} and {7,8,9} are mixed up when using them to fill in the first rows of B2 and B3.

With the use of pure and mixed top rows, twenty possibilities occur. With this, they try and complete the first band.

(Note: the permutation of B1 remains fixed)

There are  (3!)6 ways to complete the first band in terms of the the pure top row 1,2,3;{4,5,6};{7,8,9}.

The cases of the mixed top rows are more complicated. Let’s consider the top row 1,2,3;{4,6,8};{5,7,9}. This can be completed to the first band as in Fig. 3 , where a, b, and c are the numbers 1, 2, 3 in any order.

Fig 3

Once a is picked, b and c are the remaining two numbers in any order, since they are in the same row. Since there are three choices for a, and the three digits in each of the six sets in B2 and B3 can be permuted to result in various valid first bands, the total number of configurations in this case is 3×(3!)6. You can similarly work out each of the remaining seventeen cases of first rows to obtain the same number.

Now we have the number of possible first bands given the standard B1: it is 2×(3!)6+18×3×(3!)6=2612736, where the first part of the sum is the number of first band completions from the pure top rows and the second is the number of first band completions from the mixed top rows.

Instead of calculating how many full grid completions each of these 2612736 possibilities has, Felgenhauer and Jarvis next determined which first bands share the same number of full grid completions. Such an analysis reduces the number of first bands that need to be considered when counting.

Here are some operations which leave the number of grid completions of the first band unchanged: relabeling the numbers, permuting any of the blocks in the first band, permuting the columns within any block, and permuting the three rows of the band. When any of these changes B1, we can relabel the digits to recover its standard form.

Permuting B1, B2, and B3 preserves the number of grid completions because if we start with any valid Sudoku grid, the only way to keep it valid would be to permute B4, B5, B6 and B7, B8, B9 correspondingly so that the stacks remain the same. In other words, every valid grid completion for the first band gives exactly one valid grid completion for the first band being any permutation of B1, B2, B3.

Such considerations allow us to reduce the number of specific first bands we need to consider when counting. Following Felgenhauer and Jarvis, we permute the columns of B2 and B3 so that the top row entries of each are in increasing order, and then swap B2 and B3 if necessary to make the first entry of B2 smaller than that of B3. This is called lexicographical reduction. Since there are 6 permutations of the columns in each of the two blocks and two ways to permute the blocks, lexicographical reduction tells us that, given a first band, there are 62×2=72 other first bands with the same number of grid completions. So now we only need to consider 2612736/72=36288 first bands.

For each of these possibilities, we consider permutations of all three top blocks: there are 6 of them. For each of these, there are 63 permutations of the columns within each block. After performing these operations, we relabel to get B1 back into standard form. We can similarly permute the top three rows of the band, and relabel to get B1 back into standard form. These operations preserve the number of grid completions of a first band. Felgenhauer and Jarvis used a computer program to determine that these operations reduce the number of first bands to be considered from 36288 to just 416.

The main point is that the band you started with and the different band you ended with have the same number of completions to a full Sudoku grid. So instead of calculating the number of grid completions for each of these bands, we can count it for just one of them.

There are more steps that reduce the number of grids to be considered. If we have a pair of digits {a,b} in one column with a in the ith row and b in the jth row, and the same pair in a different column with b in the ith row and a in the jth row, then swapping the places of a and b in each pair will result in a band that has the same number of grid completions as the original. This is because each pair lies in the same column, and swapping both at once keeps the One Rule satisfied for the rows involved as well. As an example, look at the numbers 8 and 9 in the sixth and ninth columns of the above example. Considering all possible cases of this left Felgenhauer and Jarvis with 174 out of the 416 first bands with which to proceed.

They also considered other configurations of the same set of digits lying in two different columns or rows, which can be permuted within their columns or rows leaving the number of grid completions invariant. This reduced the number of first bands to consider to 71, and searching through each of these 71 cases let them know that there are actually only 44 first bands whose number of grid completions need to be found. Each of these 44 bands has the same number of completions to a full grid.

Let C stand for one of these 44 bands. Then the number of ways that C can be completed to a full Sudoku grid can be calculated: call it nc. We also need the number mC of first bands that share this number nC of grid completions. Then the total number of Sudoku grids will just be N=ΣCmCnC, or the sum of mCnC over all of the 44 bands.

Felgenhauer and Jarvis wrote a computer program to carry out the final calculations. They computed the number N1 of valid completions with B1 in standard form, starting with the 44 bands. Then they multiplied this number by 9! to get the answer. They discovered that the number of possible 9 by 9 Sudoku grids is N=6670903752021072936960 which is approximately 6.671×1021.

Works Cited