I have proven now $f(n)\ge 2^n-1,n\ge 1$ and $f(n)\ge 2^n+3, n\ge 3$, which is also another proof for $f(n)=1,3,10,\dots$ now, and the best lower bound I have.

Using digits $d=\{1,2,4,8,16,\dots,2^{n-1}\}$ this can be shown.

The answer is $f_d(n)+1$ by definition.

$f_d(n)=2^n-1$ for $n\ge1$ is the best bound. Then as you increase $n\ge k$ we get $f_d(n)=2^n-1+g(k)$ where $g(k)=0,0,3,11,45,533,\dots$

How to find $g(k)$?

That is, I have that smallest number not representable by $d=\{1,2,4,8,\dots,2^{n-2},2^{n-1}\}$ is $f_d(n)+1$ where $f_d(n)=2^n-1+g(k)$.

The Main Question is: Can we find $d$ such that we can show $f_d(n)$ grows even faster than the above one for $\{1,2,4,8,\dots,2^{n-2},2^{n-1}\}$ ?

Regarding improving the lower bound on my newest problem.

If $b=2$, $3\log_2 N$ bound is given: https://arxiv.org/pdf/1310.2894.pdf and explained: " The upper bound can be obtained by writing $N$ in binary and finding a
representation using Horner’s algorithm."

So if we actually allow $\le b$ digits, we have $log_b N$ digits and that many bases, so the bound would be $2\log_b N$? https://en.wikipedia.org/wiki/Horner%27s_method @TheSimpliFire

Yes but this does not translate to $f(n)\ge b^{n/2}$ since we have a fixed set of digits $d$ sadly. This is only true if $b=2$ and $d={1}$ but then $b^{n/3}=2^{n/3}$.

I think.

The problem is inverting the bound which is not trivial if $b\ne 2$.

For example, we can build $1=2-1$ using $1,2$ digits but adding onto $5$ and having now a set $1,2,5$ does NOT allow to rebuild $1$ since all digits must be used.