snippetMinor
How to solve this recurrence involving binomial coefficients?
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)$?
$$
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.
$$
$$
\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.