Return to Question

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

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

Consider the following code to compute $\binom{n}{k}$:

int binom(int n, int k) { // Required: n >= k >= 0  
  if ((k == 0) || (n == k))
    return 1;

  return binom(n−1, k) + binom(n−1,k-1);
}

I want to know how many times "+" is performed and how many recursive calls are performed. To this end, I need to solve the following recurrence, where $c$ is a constant non-negative integer, and $n$ and $k$ are non-negative integers.

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

How to solve this recurrence?

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

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

Consider the following code to compute $\binom{n}{k}$:

int binom(int n, int k) { // Required: n >= k    
  if ((k == 0) || (n == k))
    return 1;

  return binom(n−1, k) + binom(n−1,k-1);
}

I want to know how many times "+" is performed and how many recursive calls are performed. To this end, I need to solve the following recurrence, where $c$ is a constant non-negative integer, and $n$ and $k$ are non-negative integers.

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

How to solve this recurrence?

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

Consider the following code to compute $\binom{n}{k}$:

int binom(int n, int k) { // Required: n >= k >= 0  
  if ((k == 0) || (n == k))
    return 1;

  return binom(n−1, k) + binom(n−1,k-1);
}

I want to know how many times "+" is performed and how many recursive calls are performed. To this end, I need to solve the following recurrence, where $c$ is a constant non-negative integer, and $n$ and $k$ are non-negative integers.

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

How to solve this recurrence?

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