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:

enter image description here

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.


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}, $$


$$ 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} $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.