How to solve a recurrence relation for all $k$ First time posting on StackExchange. :)
How might I go about solving the following recurrence relation for all $k$?
\begin{align}
T(n) = 1 + \sum_{i=n-k}^{n-1}T(i)
\end{align}
with the condition
\begin{align}
T(i) = 1 \text{ for } i\leq k
\end{align}
Thanks!
 A: It turns out there actually is an explicit solution to this recurrence relation, involving a sum of binomial coefficients and powers of 2. The derivation of this explicit solution is based on the fact that the  generating function for the sequence is rational and has a denominator with a nice form, in particular, having only three terms.
The $k$-th order, linear recurrence relation that the OP stated is
\begin{align*}
\text{initial condition:}&&t_n&=1&&\text{ for }0\le n\le k-1\\
\text{weights:}&&w_n&=1&&\text{ for }1\le n\le k\\
\text{non-homogeneous terms:}&&b_n&=1&&\text{ for }n\ge k\\
\text{general terms:}&&t_n&=b_n+\sum_{i=1}^k t_{n-i}w_i&&\text{ for }n\ge k
\end{align*}
(Note that there's a shift in that $t_n$ coincides with the OP's $T_{n+1}$.) In any case, it is convenient to take $w_0$ to be -1 so that the recurrence relation becomes
$$ -b_n=\sum_{i=0}^k t_{n-i}w_i\text{ for } n\ge k.$$
It is important to notice that the right hand side of this relation is a convolution of the terms for the $t$'s and $w$'s.
Towards a generating function solution define the following:
\begin{align*}
\text{initial conditions:}&&I(x)&=\sum_{n=0}^{k-1}t_nx^n\\
\text{weights:}&&W(x)&=\sum_{n=0}^k w_nx^n\\
\text{non-homogeneous terms:}&&B(x)&=\sum_{n\ge k}b_nx^n\\
\text{general terms:}&&F(x)&=\sum_{n\ge0}t_nx^n.
\end{align*}
As usual, to convert the recurrence relation to a statement about the generating functions, you multiply each instance of the recurrence relation by the appropriate power of $x$ and sum over the relevant $n$'s, in this case $n\ge k$. The left side is just the negative of $B(x)$, and the right side is the product of $W(x)$ and $F(x)$ with the exception of the terms with order less than $k$. So,
$$-B(x)=W(x)\cdot F(x)-[W(x)\cdot I(x)]{\upharpoonright x^{<k}}.$$
Then, the desired generating function is 
$$F(x)=\frac{[W(x)\cdot I(x)]{\upharpoonright x^{<k}}-B(x)}{W(x)}.$$
As a sidenote, it's worth mentioning that the generating function for any $k$-th order, linear recurrence relation can be obtained in this manner. However, at this stage we'll concentrate on the initial conditions, weights and non-homogeneous terms that the OP specified. For instance, with the stated initial conditions, $I(x)$ is a finite geometric series, namely
$$I(x)=\frac{1-x^k}{1-x}.$$
The weights also lead to a finite geometric series (except for the zero term), resulting in
$$W(x)=-1+\frac{x(1-x^k)}{1-k}.$$
The non-homogeneous terms lead to an infinite geometric series, namely
$$B(x)=\frac{x^k}{1-x}.$$
After some basic algebraic simplification, this all gives
$$F(x)=\frac{1+(k-1)x^k-\sum_{i=1}^{k-1}x^i}{1-2x+x^{k+1}}.$$
In many cases, it is difficult to extract the coefficients of rational functions via partial fractions decomposition because the denominator has no obvious factorization. However, in this case the denominator has just three terms, and so this generating function can be expanded as a geometric series with ratio $x(2-x^k)$ and then the powers  $(2-x^k)^i$ can be expanded with the binomial theorem. Thus,
\begin{align*}
F(x)&=\left(1+(k-1)x^k-\sum_{i=1}^{k-1}x^i\right)\sum_{i\ge0}x^i(2-x^k)^i\\
&=\left(1+(k-1)x^k-\sum_{i=1}^{k-1}x^i\right)\sum_{i,\,j}x^i\binom ij2^j(-1)^{i-j}x^{k(i-j)}.
\end{align*}
Extracting the coefficient of $x^n$ from the double sum over $i$ and $j$  is somewhat nettlesome, but after some algebraic manipulation it turns out to be a sum of binomial coefficients and powers of 2 that for convenience we'll name $c_n$, namely
\begin{align*}
c_n&=[x^n]\sum_{i,j}x^i\binom ij2^j(-1)^{i-j}x^{k(i-j)}\\
&=\sum_{i=0}^{\lfloor n/k\rfloor}\binom{n-ik}{i}2^{n-(k+1)i}(-1)^i.
\end{align*}
(Aside: it would be great to know if the sum for $c_n$ has a simpler form!)
Then, the explicit solution for the general term $t_n$ in the original recurrence relation is
\begin{align*}
t_n&=[x^n]F(x)\\
&=c_n+(k-1)c_{n-k}-\sum_{i=1}^{k-1}c_{n-i}.
\end{align*}
I used Maple to compute $t_{50}$ in the case that $k=10$, first as defined by the recurrence relation and second by the explicit solution. In both cases the result was $t_{50}=10\,834\,552\,924\,161$.
