# How to solve this recurrence involving binomial coefficients?

How to solve the following recurrence involving binomial coefficients, where $c$ is a constant non-negative integer, and $n$ and $k$ are non-negative integers ($n \ge k \ge 0$)?

$$A(n,k) = A(n-1,k) + A(n-1,k-1) + c, \\ A(n,0) = 1, A(n,n) = 1$$

My Attempt: Without the constant $c$ (or $c=0$), $A(n,k)$ is just $\binom{n}{k}$.

I have tried the generating function $$g(x,k) = \sum_{n=0}^{\infty} A(n,k) x^n.$$ I need to evaluate \begin{align} \sum_{n=0}^{\infty} A(n+1,k) x^n &= \sum_{n=0}^{\infty}\big(A(n,k)+A(n,k-1) + c\big)x^{n} \\ &= g(x,k) + g(x,k-1) + \frac{c}{1-x} \end{align}

On the other hand, \begin{align} \sum_{n=0}^{\infty} A(n+1,k) x^n = \frac{1}{x} \big(\sum_{n=1}^{\infty} A(n,k) x^n\big) = \frac{1}{x}\big(\sum_{n=0}^{\infty} A(n,k) x^n - A(0,k)\big). \end{align} How to handle with $A(0,k)$? How to establish an equation for $g(x,k)$?

Let us guess that $A(n,k) = \alpha \binom{n}{k} + \beta$. The recurrence reads $$\alpha \binom{n}{k} + \beta = \alpha \binom{n-1}{k} + \beta + \alpha \binom{n-1}{k-1} + \beta + c,$$ from which we deduce $\beta = -c$. The base cases are $$\alpha \binom{n}{n} - c = \alpha \binom{n}{0} - c = 1,$$ From which we deduce $\alpha = c+1$. All in all, the solution is $$A(n,k) = (c+1) \binom{n}{k} - c.$$
• Are there any clues for you to guess that $A(n,k) = \alpha \binom{n}{k} + \beta$? – hengxin Apr 5 '18 at 9:29
• Experience. Perhaps more interesting is to solve the recurrence when $A(n,0) \neq A(n,n)$. – Yuval Filmus Apr 5 '18 at 9:30
• I just found that I have made a mistake: The initial conditions should be $A(n,0) = A(n,n) = 0$ instead of $A(n,0) = A(n,n) = 1$. $A(n)$ aims to count the number of additions in computing $\binom{n}{k}$ following the identity $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$. I failed to apply your method with such initial conditions. Therefore, I have removed the code and the backgroud, leaving only the recurrence to solve. However, can you solve this recurrence with the new initial conditions? (Maybe I should open a new post.) – hengxin Apr 5 '18 at 11:28
• I have obtained that $A(n,k) = c\binom{n}{k} - c$. Thanks. – hengxin Apr 5 '18 at 11:55