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

Question

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

Answer 1

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.