Evaluating the sum of large coefficients of a generating function

Question

Evaluate

$$\sum_{k=1}^{100} S_k, \; S_k = \text{coefficient of} \; x^{100} \; \text{in the series representation of} \; \left(\sum_{t=1}^\infty \left(\frac{x}{1-x} - x^k\right)^t = \frac{-x + x^k - x^{k+1}}{-1 + 2x - x^k + x^{k+1}}\right)$$

I derived the above summation when working on the following problem:

Randomly choose a number from the set $\{1, 2, 3, 4, ..., 100\}$. Now get rid of all compositions of $100$ containing that number. What is the expected value of the sum of all remaining compositions?

The coefficients of the summation are obviously extraordinarily large, so brute force computation (although possible) is not what I seek. I suspect there is a nice closed form for the summation (for example, $3^{100}$). Furthermore, I'm not sure if $100$ is just an arbitrary number or has special properties, so if this can be extended generally for all $n$, I'd love to see!

The coefficients seem to follow some kind of pattern but not enough for me to come up with a general representation. For example, for $k=1$, the coefficients form the Fibonacci sequence, and for $k>1$, there seems to be some kind of summation of previous terms to get the next. But I'm unable to put my finger on exactly what is happening.

Note: I am specifically looking for a way to evaluate the summation and not alternative ways to solve the original problem i.e the problem on the expected value of compositions.

Answer 1

This is not an answer but it is too long for comments.

Let $$\Sigma_m=\sum_{k=1}^{m} S_k$$

Suprisingly, it is not so large $$\Sigma_{100}=59593883622412940379239150329953$$ considering that $S_1$ is already equal to $218922995834555169026$

What seems to be interesting is that $\Big[\Sigma_{m+1}-2\,\Sigma_{m}+\Sigma_{m-1}\Big]$ is maximum for $m=5$

Another remark $$m\log(\Sigma_{m})\sim k\, (m-1)\qquad \qquad (R^2=0.9999957)$$ and, within a relative error of $2.59\times 10^{-21}$ $$k \sim \frac{121}{10}+\frac{186}{5 \log (2)}+\frac{371 \log (2)}{30}+\frac{161}{5 \log (3)}-\frac{269 \log (3)}{10}$$

Answer 2

Coefficients of the function $$f_k(x)=\sum_{t=1}^\infty \left(\frac{x}{1-x} - x^k\right)^t=\sum_{t=1}^\infty a_k(t)x^t$$ satisfy for $k\ge2$ recurrence relations $$ a_k(n+k+1)=2a_k(n+k)-a_k(n+1)+a_k(n), $$ $$ a_k(0)=0,\ a_k(j)=2^{j-1},\ j=1,\ldots, k-1,\ a_k(k)=2^{k-1}-1, \ a_k(k+1)=2^{k}-2. $$ It can be checked in the standard way for generating functions, multiplying $f_k(x)$ on corresponding powers of $x$ and summing up.

By the recurrence relation, the next terms roughly double every step and so $a_k(n)\sim 2^{n-1}$.

Now changing number $100$ in the question to arbitrary $m$ we have that the terms in the sum are about $2^{m-k-1}2^k=2^{m-1}$ and their sum is about $m 2^{m-1}$. Numerically for large $m$ the asymptotic fits well. For example, $$ 100\cdot 2^{99}=63382530011411470074835160268800 $$ which differs from the exact value by about 6%.