# Solve the recurrence: $f(n, k) = f(n-1, k-1) + f(n-1, k) + 2^n$

This is somewhat like Pascal's triangle but with an additional $2^n$:

\left\{\begin{align*} &f(n,0)=f(n,n)=2^n-1\\ &f(n,k)=f(n-1,k-1)+f(n-1,k)+2^n \end{align*}\right.

Is there a direct formula for $f$?

I solved for $k \le 2$ but I can't spot a general pattern for what seems to be a $k$-th degree polynomial after $(2k+1)\cdot 2^n$: \begin{align*} &f(n,0)=2^n-1 \\ &f(n,1)=3 \cdot 2^n - n-4 \\ &f(n,2)=5 \cdot 2^n - \frac{n(n+7)}2 - 8 \end{align*}

First few rows of the triangle, for reference:

0
1 1
3 6 3
7 17 17 7
15 40 50 40 15
31 87 122 122 87 31
63 182 273 308 273 182 63
127 373 583 709 709 583 373 127
255 756 1212 1548 1674 1548 1212 756 255
511 1523 2480 3272 3734 3734 3272 2480 1523 511
1023 3058 5027 6776 8030 8492 8030 6776 5027 3058 1023
2047 6129 10133 13851 16854 18570 18570 16854 13851 10133 6129 2047
...
-
If it is not easy to see by playing with it, I would make it homogeneous by solving for $2^n$, taking the shifted recurrence which has a $2^{n+1}$ and replacing in this the $2^n$ in $2^n\cdot2$ by the other. Then I think it becomes a linear homogeneous with constant coefficients. You can treat this with generating function techniques. Well, generating function techniques could be applied from the beginning without making it homogeneous. – Mlazhinka Shung Gronzalez LeWy Jul 20 '13 at 2:01
I took the liberty of correcting a sign error in the expression for $f(n,2)$. – Brian M. Scott Jul 20 '13 at 2:15

As what you have found, we denote $g(n,k)=(2k+1)2^{n}-f(n,k)$, then got:

\begin{align*} &g(n,0)=1 \\ &g(n,n)=n2^{n+1}+1\\ &g(n,k)=g(n-1,k)+g(n-1,k-1) \end{align*}

which is the same with binomial coefficient but with different initial values, and we can get:

\begin{align*} &g(n,0)=1 \\ &g(n,1)=n+4\\ &g(n,2)=n^2/2+7n/2+8\\ &.....\\ &g(n,n)=n2^{n+1}+1 \end{align*}

as we can see, $g(n,n)$ is not a ploy as we thought, but then I thought may be $g(n,n)$ is a sum of bunch of ploys, as $\sum_{k=0}^{n}k\binom{n}{k}=n2^{n-1}$, then $g(n,n)=\sum_{k=0}^{n+2}(k-1)\binom{n+2}{k}+1$, but is seems not applicable well to all $g(n,k)$, then I calculated $g(n,k) just as binomial coefficient$:

1
1 5
1 6 17
1 7 23 49
1 8 30 72 129

and I found A193605, but it is not the very same but still a bunch of binomial coefficient sum.

This is what I have got so far. Hope for more ideas and further digging.

-