HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

How to solve this recurrence involving binomial coefficients?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thisinvolvingrecurrencecoefficientsbinomialsolvehow

Problem

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

Solution

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

Context

StackExchange Computer Science Q#90247, answer score: 3

Revisions (0)

No revisions yet.