3
$\begingroup$

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)$?

$\endgroup$
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Are there any clues for you to guess that $A(n,k) = \alpha \binom{n}{k} + \beta$? $\endgroup$ – hengxin Apr 5 '18 at 9:29
  • 1
    $\begingroup$ Experience. Perhaps more interesting is to solve the recurrence when $A(n,0) \neq A(n,n)$. $\endgroup$ – Yuval Filmus Apr 5 '18 at 9:30
  • $\begingroup$ 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.) $\endgroup$ – hengxin Apr 5 '18 at 11:28
  • $\begingroup$ Try again. My method works just as well in this case. $\endgroup$ – Yuval Filmus Apr 5 '18 at 11:31
  • $\begingroup$ I have obtained that $A(n,k) = c\binom{n}{k} - c$. Thanks. $\endgroup$ – hengxin Apr 5 '18 at 11:55

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.