# Pascal-like Triangle Relation

I was fiddling around with an expansion, trying to find the coefficients of a certain formula, and I found that they satisfied the following relation for $$0 \leq c \leq r$$

$$N(r,c) = \left\{ \begin{array}{lr} 1 & \text{if} \ c=r \\ 2^r & \text{if} \ c=0 \\ 2N(r-1, c) + N(r-1, c-1) & \text{if} \ 0 < c < r \end{array} \right.$$

Then I noticed that if we interpret $$r$$ and $$c$$ as row and column it makes a pascal-like triangle of the following form: and I was wondering if there exists a general way to find explicit formulae for each term of triangles such at this one?

That is to say, if we define the formula

$$N_{a,b}(r,c) = \left\{ \begin{array}{lr} 1 & \text{if} \ c=r=0 \\ b^r & \text{if} \ c=r \\ a^r & \text{if} \ c=0 \\ aN(r-1, c) + bN(r-1, c-1) & \text{if} \ 0 < c < r \end{array} \right.$$

is there a way to find $$N_{a,b}(r,c)$$ explicitly?

Edit: By observation I noticed that $$N(r,c) = N_{2,1}(r,c) = 2^{r-c}{r \choose c}$$, but I would still like to leave this post open to see if there is a general way to tackle this problem, and also to tackle $$N_{a,b}$$ more generally.

## 1 Answer

I have figured out my own solution to this problem, but its a one of those cases where the solution seems to come from nowhere.

To do so, suppose we have two variables $$X,Y$$ such that

$$XY = aY + bYX$$

then suppose there exists constants $$N_{a,b}(r,c)$$ such that

$$X^{r}Y = \sum_{c=0}^{r} N_{a,b}(r,c) YX^{c},$$

then

$$X^{r+1}Y = \sum_{c=0}^{r}N_{a,b}(r,c) (XY)(X^{c}) = \sum_{c=0}^{r}N_{a,b}(r,c) (aY + bYX)(X^{c}) = \sum_{c=0}^{r}aN_{a,b}(r,c)YX^{c} + \sum_{c=0}^{r}bN_{a,b}(r,c)YX^{c+1}$$

but this sum equals

$$\sum_{c=0}^{r}aN_{a,b}(r,c)YX^{c} + \sum_{c=1}^{r+1}bN_{a,b}(r,c-1)YX^{c}$$

which in turn equals

$$\left\{ \sum_{c=1}^{r}\left(aN_{a,b}(r,c) + bN_{a,b}(r,c-1)\right)YX^{c} \right\} + aN_{a,b}(r,0)Y + bN_{a,b}(r,r)YX^{r+1}$$

and so by comparing coefficients of $$YX^{c}$$ as $$c$$ varies we see that these constants $$N_{a,b}(r,c)$$ must satisfy (if they exist)

\begin{align*} N_{a,b}(r+1,c) = \left\{ \begin{array}{lr} 1 & \text{if} \ c=r=0 \\ aN_{a,b}(r,0) & \text{if} \ c=0 \\ bN_{a,b}(r,r) & \text{if} \ c=r \\ aN(r, c) + bN(r, c-1) & \text{if} \ 0 < c < r + 1 \end{array} \right. \end{align*}

and so we see that these constants $$N_{a,b}(r,c)$$ (if they exists satisfy exactly the relations in the Pascal-like triangle).

But we can also prove (by easy induction) that

$$X^rY = Y(a + bX)^{r}$$

and so by the binomial theorem

$$X^rY = \sum_{c=0}^{r} {r \choose c} a^{r-c}b^{c}YX^{c}$$

which proves that firstly these constants $$N_{a,b}(r,c)$$ exist, and further that

$$N_{a,b}(r,c) = {r \choose c} a^{r-c}b^{c}$$