Resolver la recurrencia: $f(n, k) = f(n-1, k-1) + f(n-1, k) + 2^n$

Question

Esto es algo como el triángulo de Pascal pero con un $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} $$

Primera filas del triángulo de referencia:

Answer 1

Como lo ha encontrado, denotamos $g(n,k)=(2k+1)2^{n}-f(n,k)$, entonces tengo:

$$ \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) como coeficiente binomial$:

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

y me encontré con A193605, pero no es el mismo, pero todavía un montón de coeficiente binomial suma.

Esto es lo que he conseguido hasta ahora. La esperanza para más ideas y más de la excavación.