RREF Combination Counter: Similarities and Connection to Pascal's Triangle

Chapter 1: the Question

How many different types of RREF are possible for a $2\times 3$ Matrix?
For example, it can be in $\begin{bmatrix}
1&0&a\\
0&1&b
\end{bmatrix}$ or even $\begin{bmatrix}
1&a&b\\
0&0&0
\end{bmatrix}$.

So what is the total count of RREFs in $2\times 3$?

Since we don't think there will be too many, we can try to write them all out:
$$
\begin{bmatrix}
1&0&a\\
0&1&b
\end{bmatrix},
\begin{bmatrix}
1&a&0\\
0&0&1
\end{bmatrix},
\begin{bmatrix}
1&a&b\\
0&0&0
\end{bmatrix}, \\
\begin{bmatrix}
0&1&0\\
0&0&1
\end{bmatrix},
\begin{bmatrix}
0&1&a\\
0&0&0
\end{bmatrix}, \\
\begin{bmatrix}
0&0&1\\
0&0&0
\end{bmatrix}, \\
\begin{bmatrix}
0&0&0\\
0&0&0
\end{bmatrix} $$ So in total, we find that there are 7 possible RREFs.

But is writing all the possibilities the best approach to this problem?
What about for $4\times5$ or $15\times 8$? Can we write out every possibilities for those larger matrices?

Can we come up with a formula to answer these questions?

Chapter 2: Breaking-Down the Problem

What do we mean when we say count the number of possible RREFs?

Let's recall the rules for RREF:

• Leftmost Non-Zero Element in a Row must be a Leading One
• All other elements in the column with a Leading One must be a Zero
• For any given row, there are no rows below it with a Leading One more to the left than the Leading One of the given row
• Every Zero-Row is at the bottom of the Matrix

From these definitions, we notice that RREF focuses only on the Leading Ones and the Zeros of the Matrix.

This means that when counting the possible combinations of RREF, we also need to only focus on the Leading Ones and Zeroes as well. 

Remembering these rules, we can now try to generate a Counting Formula.

Chapter 3: Recursive Counter Formula

You will quickly notice that trying to formulate an explicit formula, though it may be possible, is certainly more difficult than formulating a recursive pattern.
So let's try to come up with an Recursive Counting Formula:
$$F(n\times m)$$ Imagine a $n\times m$ Matrix:
$$\begin{bmatrix}
\bigcirc  &\_ & \dots& \_ \\
\_ &\_&\dots&\_\\
\vdots\\
\_&\_&\dots&\_
\end{bmatrix}$$ The first to consider is the Left-Top element.
According to our rules for RREF, this element can either be a Leading One or a Zero.

Case 1: Leading One

Let's assume it is a Leading One. This means, by definition of RREF, every element in the first column must be zeroes. Similarly, because rest of the first row cannot hold any more Leading Ones, we can consider them to all be Zeroes as well.
This leaves us with$$\begin{bmatrix}
1 &0 & \dots& 0 \\
0&\_&\dots&\_\\
\vdots\\
0&\_&\dots&\_
\end{bmatrix}$$ This leaves a smaller 'sub-matrix' of size $(n-1)\times(m-1)$.
Our goal is to find a recursive definition for $F(n\times m)$ which means we don't have to go any deeper into this sub-matrix. The total number of ways we can fill this smaller matrix will be $F((n-1)\times(m-1))$, which means that if we had a Leading One as the first element, the possible number of RREF is $$F((n-1)\times(m-1))$$

Case 2: Zero

The only other possible first element is a Zero. Like with a Leading One, this must mean that all other elements in the first column are all zeroes. However, this still allows a Leading One to appear later on in the first row (in fact, the first Leading One must always appear on the first row).
$$\begin{bmatrix}
0 &\_ & \dots& \_ \\
0 &\_&\dots&\_\\
\vdots\\
0&\_&\dots&\_
\end{bmatrix}$$ This time, the sub-matrix has order $n\times (m-1)$, meaning by same logic as before, if we had a Zero as the first element, the possible number of RREF is $$F(n\times(m-1))$$
These are the only two possible cases for the first element, which means that total number of RREF of $n\times m$ is just sum of total count for these two cases.

$$F(n\times m) = F((n-1)\times(m-1)) + F(n\times(m-1))$$

For this recursive definition to work, we need a 'starting point' to iterate back to.
Let's try to work out some general rules for simple matrices:

Consider a $1\times1$ matrix. This matrix only has one element, and following the rules of RREF, it is obvious to see that that element must be either a Leading One or a Zero.
$$\begin{bmatrix}
1 \end{bmatrix},\begin{bmatrix}
0 \end{bmatrix}$$ In other words, we find that
$$F(1\times1) = 2$$
We can also easily solve for a $n\times1$ Column Matrix by considering the rules for RREF carefully: in a single column, there can only be up to one Leading One. So a $n\times1$ will either carry a Leading One or it won't.
If the Column did carry a Leading One, the Leading One must be placed on the first row above all other zeroes. Therefore, there is only one possibility.
If the Column didn't carry a Leading One, it must mean hat every element in the RREF must be zeroes, which again leaves us only with one possibility.
$$\begin{bmatrix}
1\\0\\ \vdots \\0
\end{bmatrix},\begin{bmatrix}
0\\0\\ \vdots \\0
\end{bmatrix}$$ So, we can write that $$F(n\times1) = 2$$
We can also simply explore a $1\times m$ Row Matrix. This is little trickier than Column Matrix, but still very easy.
This time, let's consider the first element first, just like we did to find the Recursive Formula.
$$\begin{bmatrix} \bigcirc & \_ & \dots & \_ \end{bmatrix}$$ This element, again, can either be a Leading One or a Zero.
If a Leading One, there is only one possibility where every other elements are zeroes.
$$\begin{bmatrix}1&0&\dots&0\end{bmatrix}$$ If a Zero, it leaves a smaller $1\times(m-1)$ sub-matrix, which will have $F(1\times(m-1))$ possibilities.
$$\begin{bmatrix}0&\bigcirc&\dots&\_\end{bmatrix}$$ Therefore we find that
$$F(1\times m) = 1 + F(1\times (m-1))$$ We can expand the expression and reach
$$\begin{align*}
F(1\times m) & = 1 + ( 1 + F(1\times(m-2)) \\
&= 2 + F(1\times(m-2)) \\
&\vdots \\
&= m-1 + F(1\times 1) \\
&= m-1 + 2\\ \\
\therefore F(1\times m) &= m+1
\end{align*}$$ We could have also reached this conclusion by noticing that there are $m$ 'slots' where a Leading One can fit in, and that we have additional case where the matrix is all zeroes.

Notice that these three definitions are all consistent with each other:
$$F(1\times1) = F(1\times m) = F(n \times 1) = 2 \\ \Leftrightarrow \\ n = m = 1$$ This means that we only really need the latter two rules and consider $F(1\times1) = 2$ to be a special case of those rules.


With all this, we have defined our Counter Function with these three simple rules:
$$\begin{align*}
F(n\times1) &= 1\\
F(1\times m) &= m+1\\
F(n\times m) &= F((n-1)\times(m-1)) + F(n\times(m-1))
\end{align*}$$

Let's test this out on the question from the beginning: How many different types of RREF are possible for a $2\times 3$ Matrix?
$$\begin{align*}
F(2\times 3) &= F(1\times2) + F(2\times2) \\
&= F(1\times2) + F(1\times1) + F(2\times1) \\
&= 3 + 2+2 \\
&= 7
\end{align*}$$ This is exactly what we found by writing out every possibilities.

Now let's use it to compute for a larger $5\times5$ matrix.
$$\begin{align*}
F(5\times5) &= F(4\times4) + F(5\times4 ) \\
&= F(3\times3) + F(4\times3) +F(4\times3) + F(5\times3) \\  \\
&= F(3\times 3) + 2F(4\times3) + F(5\times3) \\
&= F(2\times 2) + F(3\times2) + 2(F(3\times2) + F(4\times2)) + F(4\times2) + F(5\times2) \\ \\
&= F(2\times2) + 3F(3\times2) + 3F(4\times2) + F(5\times2) \\
&= F(1\times1)+F(2\times1) + 3(F(2\times1) + F(3\times1)) + 3(F(3\times1) + F(4\times1))+ F(4\times1) + F(5\times1) \\ \\
&= F(1\times1) + 4F(2\times1) + 6F(3\times1) + 4F(4\times1) + F(5\times1) \\
&= 2 + 4*2 + 6*2 + 4*2 + 2 \\
&= 32
\end{align*}$$ Admittedly, the process is quite messy, but it is still significantly easier than having to write out 32 RREFs.
Also, you may have noticed a neat pattern of binomials appearing midst our calculation. We will explore this again later.

We can try to solve for $F(15\times 8)$ in the same way, but a calculation like that seems more fitting for a computer algorithm than for doing it by hand.

int RREFcounter(int n, int m){
    if(n == 1) return m+1;
    if(m == 1) return 2;
    return RREFcounter(n-1, m-1) + RREFcounter(n,m-1);
}

How else can we explore this Counter Function without needing these messy calculations?

Chapter 4: Similarities to Pascal's Identity and Triangle

Everyone knows Pascal's Triangle but many don't know why such a pattern generates binomial values. It works thanks to Pascal's Identity that states

$$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$ Pascal's Triangle organizes these terms so that $n$ downwards (as rows), and $k$ increases to the right (as rightwards slanted columns):

$$\begin{align*}
&&\binom{n-1}{k-1}&&&&\binom{n-1}{k}\\
&&&&\binom{n}{k}&&&&
\end{align*}$$ Filling out the triangle starting with $\binom{0}{0} = 1$ and $\binom{0}{k} = 0$, you can easily and quickly generate rest of the binomial values as the famous Pascal's Triangle:

Pascal's Triangle with rows and columns outlined

This reduces the problem of having to compute the binomial values to simple additions and look-up – much easier to do than calculating the products of factorials.

We can try to replicate the same technique to our own Counter.

Notice the striking resemblance between Pascal's Identity and our recursive definition of counter:

$$\begin{align*}
&\binom{n}{k} &= &\binom{n-1}{k-1}&+&\binom{n}{k-1} \\
&F(n\times m)&=&F((n-1)\times(m-1))&+&F(n\times(m-1))
\end{align*}$$ They both have the same structure of summing previous values to generate the next. This means we should be able to organize a similar look-up table as Pascal's Triangle.

Let's first make some notes about how we need to organize:
The addends have the same number of columns $m-1$ and their sum's column is one incremented from the addend's. This means that the column value $m$ will increase towards the bottom.
The addends have different number of rows $n$ and $n-1$ and their sum's row is the larger of the two, $n$. This means that the row value $n$ will increase towards the right. 

Rows and Columns are labeled in preparation to generate the pattern.

This might be confusing at first, because the Row in the Matrix are represented by the columns of the pattern and vise versa, but remembering that these are flipped may be an easy method for remembering it. 

Using the two starting-point rules, we can fill out the necessary values to begin generating the table:

$$F(1\times m) = m+1 \\ F(n\times 1) = 2 $$

Starting values are filled out, ready to generate the table.

Finally, we can start adding these numbers, just like with Pascal's Triangle, and form this neat Parallelogram(?)

RREF Counter Parallelogram

Before moving on any further, we notice that the right-side of the Parallelogram are just repeats of the same number. To direct our focus to the main unique values, let's dim them out.

RREF Counter's Main Triangle

With this, we can now easily answer the question: what is $F(15\times 8)$?

It comes out to be 22,819. 

And we didn't need to write out all those thousands of possible RREFs to reach this answer, nor perform messy expansion.  

Chapter 5: Expansion I 

Before moving on any further, we notice that our Parallelogram, unlike Pascal's Triangle, begins its rows and columns at index 1 not 0. We can try to fill in the missing slots like puzzle. 

First fact we will realize is that every case when $n=0$, $F(0\times m)$ should be a 1, for when $m \geq 1$ at least:

Only possible solution for $n=0$ are all 1. Any other value will not be consistent with the Recursive Defintion.

This will then lead to the obvious fact that rest of the left-hand side must be filled with zeroes:

Naturally, this leads to all Zeroes on the Left-hand side.

But, because these zeroes do not add particular value to the diagram and seems quite obvious, they will be omitted for now.

This is a natural expansion of the current pattern; however, expanding the pattern upwards is not as straight-forward. This is because there are multiple possible combinations that can validly generate rest of the pattern.

But after some trial and error, the most satisfying combination can be found:

Extended RREF Counter

This seems to be the most logical extension of the original pattern for few reasons:

Firstly, this is the simplest pattern that doesn't require alternating signs or complicated progression of pattern, which by Occam's Razor is a massive hint. 

Secondly, this was consistent with definition of the Counter Function that generates the pattern. Surely, if a matrix had no elements, the only possible RREF is a matrix with no Leading Ones and no Zeroes. This pattern was already demonstrated by $F(0\times m) = 1$. 

Also, this fits the pattern that the same number infinitely repeat towards the right. 

Also this means that we actually only need two rules to generate the Parallelogram, not three:
$$F(n \times 0) = 1 \Leftrightarrow n \geq 1\\
F(n\times m) = F((n-1)\times(m-1)) + F(n\times(m-1)) $$

Chapter 6: Patterns

RREF Counter Parallelogram

Everyone's favorite pastime is looking for fascinating patterns and phenomenas hidden in Pascal's Triangle. We can try to find similar patterns in our own Parallelogram as well! Here are few simple examples:
When $n=0$, $F(0\times m)$ are all 1.
$$F(0\times m) = 1$$ When $n=1$, $F(1\times m)$ are natural numbers.
$$F(1\times m) = m+1$$ When $n=2$, $F(2\times m)$ are one bigger than a Triangular Number.

Triangular numbers plus one highilghted

$$F(2\times m) = T_m + 1, \, T_m = \frac{(m+1)(m+2)}{2}\\
T_0 = 0 \\
T_1 = 1\\
T_2 = 3\\
T_3 = 6\\
T_4 = 10 \\ \vdots $$ The diagonal are all Powers of Two.
$$F(n\times n) = 2^n$$ In fact, the values towards the right are repeats of the Two's Power from that row.
$$F(n\times m) = 2^m, m \geq n$$ The value directly to the left of the diagonals are one less than the Power of Two, also called Mersenne Numbers.

Mersenne's Numbers and Powers of Two highlighted 

$$F((m-1) \times m ) = 2^m -1$$ Only other numbers that seems to be duplicates of (besides the trivial numbers) are the Powers of Four.

Powers of Fours highlighted

$$F(n\times (2n+1)) = 4^n$$
Though no real pattern is found, here are highlights of Primes:

Primes highlighted. No obvious pattern.

Though patterns for primes are difficult to spot right away or even confirm at this small scale, few interesting observations about when primes don't occur can be made.
The columns, $n=3,\,5,\,7$ seems to never carry primes. However, this is still merely a speculation made from a small sample.

We can also find something analogous to the Christmas-Stocking Theorem for Pascal's Triangle:

Telephone Theorem

$$\sum_{i=a}^b F(n \times i) = F((n+1)\times(a+1)) - F((n+1) \times b)$$

Visualization of Telephone Theorem. Sum of the Red-highlight is equal to the difference of the Blue-Highlights in each 'telephone'. . 

$$\begin{align*}
\sum_{i=7}^{14}F(2\times i) &= 29 + 37 + 46+56+67+79+92+106 \\
&= 512 \\
&= 576 -64 \\
&= F(3\times 15) - F(3\times7) \\ \\
\sum_{i=0}^{4}F(3\times i) &= 1+2+4+8+15 \\
&= 30 \\
&= 31-1\\
&= F(4\times5) - F(4\times0)\\ \\
\sum_{i=6}^{12} F(5\times i ) &= 63+120+219 + 382+638 + 1024 + 1586 \\
&= 4032\\
&= 4096 - 64 \\
&= F(6\times 13) - F(6\times 6) \\
&\vdots \end{align*}$$ I will demonstrate the proof for both Telephone and Christmas-Stockings Theorem in a later article, but both can be easily proven utilizing Essence Transformation (more about Essence and Sequence Curves here: Sine and Cosine Series).

Telephone Theorem holds true along other direction of diagonal as well. You can represent them in various ways:

$n$-Bound

$$\sum_{i = a_n}^{b_n} F(i \times (m+i)) = F( b_n \times (m+b_n+1)) - F((a_n-1)\times (a_n+m))$$

$m$-Bound

$$\sum_{i=a_m}^{b_m} F( (n + i) \times i ) = F( (n+b_m) \times (b_m+1) ) - F((n + a_m - 1)\times a_m)$$

Terms Bound

$$\sum_{i=0}^x F((n+i)\times (m+1)) = F((n+x)\times(m+x+1)) - F((n-1)\times m)$$ Remember that since index starts at 0, we are adding $x+1$ number of terms.

These three all represent the same concept, but focusing on different values. Terms-Bound defintion seems the 'cleanest' and simplest, so we will use it to verify that the formula works.

Visualization of Telephone Theorem in Leftwards Diagonals. 

$$\begin{align*}
\sum_{i=0}^4 F(i \times (3+i)) &= 1+5+16+42 + 99\\
&= 163\\
&= 163 - 0\\
&= F(4\times 8) - F(-1 \times 3) \\ \\
\sum_{i=0}^5 F((3+i)\times(9+i)) &= 130+386 +1024 + 2510 + 5812 + 12911 \\
&= 22773 \\
&= 22819  - 46 \\
&= F(8 \times 15) - F(2 \times 9) \\ \\
\sum_{i=0}^{5}F((5+i)\times(2+i)) &= 4+8+16+32+64+128 \\
&= 252 \\
&= 256 - 4 \\
&= F(1\times8) - F(4\times 2) \\ \\
\sum_{i=0}^5 F((8+i)\times(7+i)) &= 128 + 256 + 512 + 1024 + 2048 + 4096 \\
&= 8064 \\
&= 8192 - 128 \\
&= F(13\times 13) - F(7\times7) \\
&\vdots
\end{align*}$$

These are just some of the patterns that can be noticed right away.
I challenge you to try to discover other interesting sequences and patterns that are generated from this simple formula.

Chapter 7: Expansion II

Now that we have found some basic patterns, we can extend those patterns to negative $m$. We needed to find these patterns first because there are many valid ways of filling in the rows above $m=0$. Following the existing patterns assures us that our prediction about Extended Parallelogram is correct. 

We noticed two major patterns for Rightwards Columns and Leftwards Diagonals. 

We will first focus on the Rightwards Column's Pattern that every value in the zeroth column is a 1:

$$F(0\times m) = 1$$

Pattern of the 0th Column extended to negative m. 

This allows us to fill out a unique valid pattern for rest of the values:

Parallelogram Expansion following Column Rule

This is our first fully Expanded Parallelogram.

Interestingly, by just following the pattern for $n=0$, columns' pattern for $n=1,2$ and presumably every other columns are all maintained still. 

It is interesting to note that $n=2$ column which are one larger than a triangular number are completely symmetric. This seems to be the only column, besides $n \leq 0$ that shares this characteristics. 

Now that the Parallelogram's previously unknown region is filled out, we can again start hunting for interesting patterns.

Chapter 8: Patterns II

Parallelogram Expansion following Column Rule

When $m=-1$, $F(n \times -1)$ alternates from 1 and 0. There are few different ways of representing this:
$$\begin{align*} F(n \times -1) &= \frac{1}{2} - \frac{1}{2}(-1)^n \\
&= \frac{1}{2} +  \frac{1}{2}\cos(\pi n) \end{align*}$$ When $m=-2$, $F(n\times -2)$ covers every Integer. This also has many ways of representation: 
$$\begin{align*}F(n \times -2) &= (-1)^n \left \lfloor \frac{n+1}{2} \right \rfloor \\
&= - \sum_{i=1}^{n} i(-1)^i \\
&= \frac{1}{2} \left ( \frac{1}{2} - (n + \frac{1}{2})(-1)^n \right )
\end{align*}$$

Every Integers appear when $m=-2$.

When $m=-3$, we notice two patterns: for odd columns we have square numbers, while for even columns, we have negative product of consecutive integers.
$$\begin{align*}F((2n-1)\times -3) &= n^2 \\
F(2n \times -3) &= -n(n+1)
\end{align*}$$ We can actually represent this more generally using $n=-2$:
$$F(n \times -3) = - F(n \times -2) * F((n+1)\times -2)$$

Pattern of Squares and Consecutive Products. 

When $n$ is odd, $F$ goes to negative when $m < 0$, but $F$ always stays positive when $n$ is even. This is easy to see why, because the sequences of the even columns are represented by Even Polynomial, and odd columns are represented by Odd Polynomials.
$$ \lim _{m\rightarrow -\infty} F( 2n \times m ) = +\infty \\
\lim_{m \rightarrow -\infty} F((2n+1) \times m) = -\infty $$

Even columns are positive, but Odd Columns are negative.

Interestingly, the Telephone Theorem still holds even in this expanded pattern, which makes sense because the theorem depends on the how this Parallelogram is generated rather than the values themselves.

Just like before, we can challenge ourselves to try to discover subtle hints of regular pattern amidst this great chaotic Parallelogram.

Chapter 9: Leftwards Diagonals

As mentioned before, the above expansion is not the only valid solution. We can also try to use patterns of the Diagonals rather than the columns to expand to the negative row $n$.

RREF Counter Parallelogram 

What are the patterns of the Diagonals then?
The main diagonal holds the sequence $1,2,4,8,16 \dots$ which are obviously the Powers of Two.
$$F(n\times n) = 2^n$$ The First Diagonal below it holds the sequence $1,3,7,15,31\dots$ which again is simply one less than a power of two.
$$F(n\times (n+1)) = 2^{n+1}-1$$ But what about the Second Diagonal?
Then what about the Third?

Patterns for those diagonals aren't as obvious or are as easy to describe as the columns (which can be represented as finite polynomial). How can formulate the patterns of the Diagonals?

Let's define a function that generates sequence of the diagonals (Diagonal Generator Function):
$$Ɛ^n(x) = F( (n+x)\times x )$$ or in words, $Ɛ^n(x)$ yields $x$th element in the $n$th diagonal.

Diagonal Generator Visualized

And we already know the $Ɛ^0$ and $Ɛ^1$:
$$Ɛ^0(x) = 2^x \\
Ɛ^1(x) = 2^{x+1}-1 $$
How do we generate the rest of $Ɛ^n$?

Remember that the numbers of these sequences are generated by the same rule of Pascal's Triangle:
$$F(n\times m) = F((n-1)\times (m-1)) + F(n\times (m-1))$$ This can be nicely translated to
$$Ɛ^n(x) = Ɛ^n(x-1) + Ɛ^{n-1}(x)$$ We also notice that when $Ɛ^{n}(0)=1$, at leasts when $n \geq 0$.
With these observations we find that
$$\begin{align*}
Ɛ^n(0) &= 1\\
Ɛ^n(1) &= 1 + Ɛ^{n-1}(1) \\
Ɛ^n(2) &= 1 + Ɛ^{n-1}(1) + Ɛ^{n-1}(2)\\
&\vdots \\
\therefore Ɛ^n(x) &= 1+Ɛ^{n-1}(1)+\dots +Ɛ^{n-1}(x)\\
&= Ɛ^{n-1}(0) + Ɛ^{n-1}(1) + \dots + Ɛ^{n-1}(x) \\
&= \sum_{i=0}^x Ɛ^{n-1}(i)
\end{align*}$$ We can represent this series as a continuous and differentiable formula using Essence Transformation (check our more on Essence of Exponentials):
$$Ɛ^n(x) = \sum_{i=0}^xƐ^{n-1}(i) = \int_{-1}^x Ȣ\left \{ Ɛ^{n-1}(t)\right\} dt$$ However, knowing how to use Essence Transformation won't be necessary to follow the process. I will provide only the necessary tricks and tips for computing the series.

With these givens, we can start generating all $Ɛ^n(x)$, but it will be much more helpful to use these two tricks to help us calculate:

Series of Exponentials of Two

$$\sum_{i=0}^n 2^{i+k} = 2^{n+k+1} - 2^{k}$$

Power Series as Matrix Multiplication

We can represent any Series of Polynomial as matrix multiplication of Row and Column Matrices with Inverse of a Square Matrix with Values from Pascal's Triangle, which I call Pascal's Matrix.
Pascal's Matrix of order $n$ is generated by putting numbers from Pascal's Triangle until the $n$th row upside-down into a square matrix, removing the first ones:
$$P_1  =\begin{bmatrix}1
\end{bmatrix}\\
P_2 = \begin{bmatrix}
2&1\\
0&0
\end{bmatrix} \\
P_3 = \begin{bmatrix}
3&3&1\\
0&2&1\\
0&0&1
\end{bmatrix} \\
P_4 = \begin{bmatrix}
4&6&4&1\\
0&3&3&1\\
0&0&2&1\\
0&0&0&1
\end{bmatrix} \\
\vdots
$$ Using these Matrices, you can compute a large series at once as such:

Let's say you want to calculate
$$\sum_{x=8}^{29} 5x^3+ 7x^2 + 9$$ We need three components to calculate this. We first need to notice that the Degree of the Polynomial is 3. We need to use Pascal's Matrix of  One order larger than the degree, so in this case $P_4$. In our calculation we need to use the Inverse of this Matrix $P^{-1}_4$.

Our second component is a Row Matrix of the coefficient. In our case, it is
$$C = \begin{bmatrix}5&7&0&9\end{bmatrix}$$ Notice that number of columns is again one larger than the degree.

Our final component is Column Matrix composed of the Bounds. One will be added to the upper bound, while lower bound remains the same. The column matrix is made of difference between that upper bound raise to a power and lower bound raised to the same power. The highest power it is raised to is again one bigger than the original degree:
$$B= \begin{bmatrix}
(29+1)^4 - 8^4 \\
(29+1)^3 - 8^3\\
(29+1)^2 - 8^2\\
(29+1) - 8
\end{bmatrix}$$
These three components come together to compute the series as such:
$$\sum_{x=8}^{29} 5x^3 + 7x^2 + 0x + 9 =  \begin{bmatrix}5&7&0&9\end{bmatrix}\begin{bmatrix}
4&6&4&1\\
0&3&3&1\\
0&0&2&1\\
0&0&0&1
\end{bmatrix}^{-1} \begin{bmatrix}
(29+1)^4 - 8^4 \\
(29+1)^3 - 8^3\\
(29+1)^2 - 8^2\\
(29+1) - 8
\end{bmatrix}$$ where the middle Matrix is the Inverse of Pascal's Matrix.
When we calculate the multiplication, it yields
$$\begin{bmatrix}5&7&0&9\end{bmatrix}\begin{bmatrix}
4&6&4&1\\
0&3&3&1\\
0&0&2&1\\
0&0&0&1
\end{bmatrix}^{-1} \begin{bmatrix}
(29+1)^4 - 8^4 \\
(29+1)^3 - 8^3\\
(29+1)^2 - 8^2\\
(29+1) - 8
\end{bmatrix} = \begin{bmatrix}
1001308
\end{bmatrix}
$$ which is exactly what the series adds up to.
$$\sum_{x=8}^{29} 5x^3 + 7x^2 + 0x + 9 = 1001308$$ and we found the result without having to use multiple messy Induction Formulas.

This works for any degree Polynomial in general:
$$\sum_{i=n}^m \left\{c_k x^k + c_{k-1}x^{k-1} + \dots c_{0} \right \}= \begin{bmatrix}
c_k & c_{k-1} & \dots & c_{0}
\end{bmatrix} { P_{k+1} }^{-1} \begin{bmatrix}
(m+1)^{k+1} - n^{k+1}\\
(m+1)^{k} - n ^{k} \\
\vdots \\
(m+1) - n
\end{bmatrix}
$$ A more rigorous proof will be demonstrated later article involving Unit Differences and Essence Transformations, but for now knowing how to use this is more important than understanding how it works.

With these two tricks, we can easily compute all the $Ɛ^n$.
We start with $Ɛ^0(x) = 2^x$:
$$\begin{align*}
\because Ɛ^0(x) &= 2^x \\
Ɛ^1(x) &= \sum_{i=0}^x 2^i \\
&= 2^{x+1} - 2^0, \text{ by Series of Exponentials of Two trick} \\
&= 2^{x+1} - 1\\
Ɛ^2(x) &= \sum_{i=0}^x 2^{i+1} - 1 \\
&= 2^{x+2}-2^1 + \begin{bmatrix}
-1
\end{bmatrix}\begin{bmatrix}1\end{bmatrix}^{-1}\begin{bmatrix}
(x+1)^1 - 0
\end{bmatrix} \\
&= 2^{x+2}-2 + \begin{bmatrix}
-x-1
\end{bmatrix} \\
&= 2^{x+2} - x - 3\\
Ɛ^3(x) &= \sum_{i=0}^x 2^{i+2}-i-3 \\
&= 2^{x+3}-2^2 + \begin{bmatrix}
-1 & -3
\end{bmatrix}\begin{bmatrix}
2&1\\
0&1
\end{bmatrix}^{-1}\begin{bmatrix}
(x+1)^2\\
(x+1)
\end{bmatrix} \\
&= 2^{n+2}-4 + \begin{bmatrix}
-\frac{1}{2}x^2-\frac{7}{2}x - 3
\end{bmatrix} \\
&= 2^{x+3}-\frac{1}{2}x^2 - \frac{7}{2}x - 7 \\
Ɛ^4(x) &= \sum_{i=0}^x 2^{i+3} - \frac{1}{2}i^2 - \frac{7}{2}i - 7 \\
&= 2^{x+4}-2^3 + \begin{bmatrix}
-\frac{1}{2}& -\frac{7}{2} & -7
\end{bmatrix}\begin{bmatrix}
3&3&1\\
0&2&1\\
0&0&1
\end{bmatrix}^{-1}\begin{bmatrix}
(x+1)^3\\
(x+1)^2\\
(x+1)
\end{bmatrix} \\
&= 2^{x+4} - 8 + \begin{bmatrix}
-\frac{1}{6}x^3 - 2x^2 - \frac{53}{6}x - 7
\end{bmatrix}\\
&= 2^{x+4} - \frac{1}{6}x^3 -2x^2 - \frac{53}{6}x - 15 \\
&\vdots
\end{align*}
$$ and so on and so on.
These formulas successful generate all elements in the sequence of the diagonals.

They also have a neat property that
$$Ɛ^n(1) = n+2$$ which derives from the pattern generated by the Columns of the Parallelogram.

Chapter 10: Tri-State Function

These Diagonal Formulas is not only accurate for positive $x$, but they are also consistent with the expanded Parallelogram from Chapter 5: Expansion I.

Negatives of Diagonal Generator

However, by following these formulas, we learn that these zeroes do not extend forever.
In fact, filling out the Parallelogram using the patterns of the diagonals reveal:

Zeroes of Diagonal Generator are finitely many. 

Rest of the expansion will not be shown here because the fractions and signs make the diagram too messy.

First point of interest is that $Ɛ^n$ has finite number of Zeroes.
In fact $Ɛ^n(x)$ has consecutive $n$ Zeroes from integers $-1$ to $-n$ and nowhere else.
This fact is better demonstrated visually by graphing those equations, for example through Desmos (Click here to see the graphs).

You may be thinking, why is this so special?
You might say, 'we can easily come up with $n$ consecutive Zeroes by simply doing:'
$$(x+1)(x+2)\dots(x+n)$$
Though you are correct, our $Ɛ^n$ holds unique properties that those polynomials do not.

Firstly, $Ɛ^n$ cannot be represented as finite Power Series. Unlike the $(x+1)(x+2)\dots(x+n)$, because our $Ɛ^n$ involves an Exponential term, it is much more difficult to approximate or even guess to a satisfying precision with a polynomial.

Secondly, unlike the $(x+1)(x+2)\dots(x+n)$, the $Ɛ^n$ is much more 'stable', by which I mean when $x$ is near a Zero of $Ɛ^n$, then the value of $Ɛ^n(x)$ is extremely close to 0 as well. This is not always the case with Polynomials.
The polynomial $(x+1)(x+2)\dots(x+n)$ may be 'bumpy' even though $x$ may be near a Zero. For $Ɛ^n$, however, when $x$ is near a Zero, the curve forms relatively 'smooth' wiggle around the x-axis. In fact, as you increase $n$, the $Ɛ^n$ seems to 'wrap' itself around the axis, eventually completely merging with the $y=0$ itself.
Of course, you could simply multiply the polynomial by $\frac{1}{n!}$ to smooth it out, but $Ɛ^n$ still turns out to be a little bit smoother than $\frac{1}{n}(x+1)(x+2)\dots(x+n)$.

These properties combined give rise to an interesting function as $n$ approaches $\infty$, which I will call Tri-State Function.
$$
\lim_{n\rightarrow \infty} Ɛ^n(x) =
\begin{cases}
      0 & x< 0 \\
      1 & x = 0 \\
      \infty & x > 0
   \end{cases}
$$
Because the trend of $Ɛ^n$ is so smooth, even if $n$ isn't quite approaching $\infty$, a fairly good approximating can be made:
$$Ɛ^n(x) \approx \begin{cases}
      0 & x< 0 \\
      1 & x = 0 \\
      \infty & x > 0
   \end{cases}, x\in [-n, \infty)
$$ This ability to check three cases numerically is, I believe, a powerful tool especially for computer science and other fields where approximation of if-statements is useful.

Chapter 11: Negative $n$

So far, we restricted our $n$ of $Ɛ^n(x)$ to be always greater than 0. However we can extremely easily expand to negative values.
For that let's be introduced to another useful tool introduced in my Essence Series: Unit Difference.
$$Ud\{ f(x) \} = f(x+1) - f(x)$$ We can easily interpret Unit Difference as asking, how much do we need to increment the current term to get the next term in the sequence?
$$f(x+1) = f(x) + Ud\{ f(x) \}$$ This becomes very useful when dealing with series as you will see here.

We found our general rule that
$$Ɛ^n(x)= \sum_{i=0}^x Ɛ^{n-1}(i)$$ We can apply Unit Difference to both sides and get
$$\begin{align*}
Ud_x\{ Ɛ^n(x) \} &= Ud_x\left\{ \sum_{i=0}^x Ɛ^{n-1}(i) \right\} \\
&= \sum_{i=0}^{x+1} Ɛ^{n-1}(i) - \sum_{i=0}^x Ɛ^{n-1}(i) \\
&= Ɛ^{n-1}(x+1)
\end{align*}$$ There we can find that
$$ Ɛ^{n-1}(x) = Ud_x \{  Ɛ^{n}(x) \} $$
Interestingly, Exponentials of Two have an interesting property that
$$\begin{align*}
Ud\{ 2^x\} &=  2^(x+1) - 2^x \\
&= 2^x(2-1)\\
&=2^x
\end{align*}$$ they are their own Unit Difference (quite analogous to how $\frac{d}{dx}e^x = e^x$).
This means that we can very easily find that
$$\begin{align*}
\because  Ɛ^0 (x) &= 2^x \\
 Ɛ^{-1}(x) &= Ud\{ 2^(x-1)\} \\
&= 2^{x-1} \\
 Ɛ^{-2}(x)  &= Ud\{2^{(x-1)-1} \} \\
&= 2^{x-2} \\
&\vdots \\
 Ɛ^{-n}(x) &= 2^{x-n}, n\in \mathbb{N}
\end{align*}$$ which is a convincing argument for why same Powers of Two repeat to the right of the Parallelogram.

However this means that for $n < 0$, the value of $Ɛ^{n}(0) \neq 1$. In fact, for $n<0$, we get $Ɛ^{n}(0)  = 2^n$, which is not as satisfying as result of Chapter 7: Expansion II.

Chapter 12: Connection with Binomials and Pascal's Triangle

Back in Chapter 3, we noticed binomials appearing as coefficients when expanding $F(5\times 5)$. This was no coincidence and their appearance makes more obvious sense when considering the process of expanding visually.
If we imagine drawing a line from a term to what it expands to, we get:

Visualization of Expanding the Recursive Formula.

As we expand, we find that the repeating terms add up and compound to a binomial value. This is almost like drawing an Upside-Down Pascal's Triangle.
After however many expansions, we multiply the binomial value with the known values of $F$, but we will find that it is easiest to calculate when we expand until the 0th row, where every value is either a 0 or a 1 (as shown above):
$$\begin{align*}
F(5\times 5) &= \binom{1}{0}F(5\times 4) + \binom{1}{1}F(4\times 4) \\
&= \binom{2}{0} F(5\times 3) + \binom{2}{1}F(4\times 3) + \binom{2}{2}F(4\times 2) \\
&\vdots \\
&= \binom{5}{0}F(5\times 0) + \binom{5}{4}F(4\times 0) + \dots + \binom{5}{5}F(0\times 0) \\
&= \binom{5}{0} + \binom{5}{2} + \dots + \binom{5}{5}  \\
&= 32
\end{align*}$$ This gives us another satisfying explanation for why Powers of 2 appear repeatedly to the right, as sum of a Row form Pascal's Triangle add up to a Power of Two:
$$\sum_{i=0}^n \binom{n}{i} = 2^n$$
The same pattern works for terms to the left of the Powers of Twos.

Visualization of Expansion of Recursive Formula. 

Again, you are still adding up the binomials, but you are just skipping some.
Which ones are we skipping then? Can we express $F$ as Series of Binomials?

First off, we know that when $F(n\times m)$, we have to expand $m$ times until we get $F(n\times 0)$. So in other words, we are looking at the $m$th row of Pascal's Triangle.
$$\binom{m}{x}$$ We also know that since $F(n\times 0) = 1$ only for $n\geq 0$, we only need to add $n$ binomials.

These two combined, we can finally represent our Counter Function as
$$F(n\times m) = \sum_{i=0}^n \binom{m}{i}$$
Interestingly, this definition agrees with Column-wise Expansion II from Chapter 7 rather than the the Diagonal Expansion from Chapter 9.
This is because $\sum_{i=n}^{n-1}f(i) = 0$ for all function $f$, therefore
$$F(-1\times m) = 0$$ for all function $f$.
 Also for $n=0$, we can also find that this new definition agrees with the column's pattern that
$$F(0\times m) = \sum_{i=0}^0 \binom{m}{i} = \binom{m}{0} = 1$$

Another interesting fact that arrises from comparing our $F$ Parallelogram to Pascal's Triangle is that you can generate our Parallelogram by imagining 'stamping'/'stacking' Pascal's Triangle side-by-side:

Pascal's Triangle sliding across and 'stamping' on its binomials to form RREF Counter Parallelogram. 

Chapter 13: Interpretation

What is our Counter actually counting?
Well, it is counting how unique RREFs are possible for a given order, but what does that even mean?
It means that given $m$ variables and $n$ equations, there are $F(n\times m)$ number of ways that the system of equations uniquely depend on the variables.

Or focusing on the Binomial Series, we can interpret $F(n\times m)$ as counting number of possible combinations of $n$ or less elements, given a set of size $m$.
Or likewise, because we can also write
$$F(n\times m) = \sum_{i = m-n}^m\binom{m}{i}$$ we can also interpret it as counting the number of possible combination of $m-n$ or more elements, given a set of size $m$.

Like with hunting for interesting patterns on Pascal's Triangle and this Counter Parallelogram, we can continue searching for more applications and interpretations of the Counter. I will leave this as fun challenge for the readers as well.