I was thinking about this problem a few days ago and in the process I came up with what I can best describe as a two-dimensional recurrence relationship. It seemed obvious to me that this was something akin to a description of Pascal's triangle, so I began to think more carefully about a recurrence relationship that would yield the binomial coefficients. I wondered what would be the output if I tinkered slightly with the nature of the recurrence relationship.
Let $t_{n,m}$ be the $m$th entry in the $n$th column of what will be a triangle like Pascal's triangle.
Example 1:
Let $t_{0,0}=1$ and let $t_{0,i}=0$ for $i \ge 1$
For $n \ge1$ let $t_{n,0}=t_{n-1,0}$ and let $t_{n,i}=t_{n-1,i}+t_{n-1,i-1}$ for $i \ge 1$
I think it's pretty obvious that $t_{n,m}$ are simply the binomial coefficients.
Example 2:
Let $t_{0,0}=1$ and let $t_{0,i}=0$ for $i \ge 1$
For $n \ge1$ let $t_{n,0}=at_{n-1,0}$ and let $t_{n,i}=at_{n-1,i}+bt_{n-1,i-1}$ for $i \ge 1$
In this case $t_{n,m}$ are the coefficients of $\left(ax+b \right)^n$.
So far the recurrence relationships have been what I guess you could call homogeneous. The next example is what I stumbled across in the other question.
Example 3:
Let $t_{0,0}=1$ and let $t_{0,i}=0$ for $i \ge 1$
For $n \ge1$ let $t_{n,0}=it_{n-1,0}$ and let $t_{n,i}=it_{n-1,i}+t_{n-1,i-1}$ for $i \ge 1$
It's intersting to see the factorials and the triangle numbers here.
I then decided to generalise as follows:
Example 4:
Let $t_{0,0}=1$ and let $t_{0,i}=0$ for $i \ge 1$
For $n \ge1$ let $t_{n,0}=hit_{n-1,0}$ and let $t_{n,i}=(a+hi)t_{n-1,i}+(b+ki)t_{n-1,i-1}$ for $i \ge 1$
My spreadsheet will calculate the values of $t_{n,m}$ but I now have no idea what they are!
To conclude, my questions are:
How can I prove that Example 1 gives the binomial coeffients?
How can I prove that Example 2 gives the coefficients of $\left(ax+b \right)^n$ ?
Can we find a way to describe $t_{n,m}$ as a function of $n, m, a, b, h, k$ ?
Is there a more general situation that has already been studied? Something like $t_{n,i}=f(i)t_{n-1,i}+g(i)t_{n-1,i-1}$