2
$\begingroup$

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!

$\endgroup$
4
  • 1
    $\begingroup$ So $k$ is fixed? That's a linear inhomogeneous recurrence relation with constant coefficients. There is a standard theory for such things that you can easily look up. The idea is based on constructing a solution to the homogeneous relation as a linear combination of exponentials, and then adding in a particular solution (which does not have to satisfy the given initial condition). Note that to do this you will need to be able to find the roots of the polynomial $p(x)=-1-x-x^2-\dots-x^{k-1}+x^k$. This is quite hard to do analytically even in $k=3,4$ and probably impossible with $k \geq 5$... $\endgroup$ – Ian Sep 30 '16 at 23:30
  • $\begingroup$ ...in which case I might suggest an asymptotic instead. $\endgroup$ – Ian Sep 30 '16 at 23:35
  • $\begingroup$ @Ian How would an asymptotic approach to this problem look? $\endgroup$ – Okonomiyaki Sep 30 '16 at 23:42
  • $\begingroup$ You would use the same theory as before to note that the solution is on the order of $r^n$ where $r$ is the largest root of the $p$ I mentioned earlier, and then attempt to estimate $r$. $\endgroup$ – Ian Sep 30 '16 at 23:59
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.