5

In the question Algorithms: Recurence Relation, the author asked about the recurrence relation $$T(n) = T(n-1) + n(n-1)$$ and one of the answers proposed assuming $T(n)$ is polynomial, then manipulating the equation to obtain the coefficients.

Question: What reason is there to suspect that this recurrence satisfies a polynomial identity? And how can we apply this to linear recurrences in general?

The Fibonacci Numbers, for example, instead satisfy a exponential solution. So, if we attempted to fit a polynomial solution, it wouldn't work.

Community
  • 1
Rebecca J. Stones
  • 26,845
  • 2
    The answers below both use the "calculus of finite differences." I would like you to know that this is not just some isolated trick. "Difference equations" (analogous to differential equations) are important in engineering and physics. You can find a good introduction in chapter 2 of Advanced Mathematical Methods for Scientists and Engineers by Bender and Orszag. – Potato Sep 07 '13 at 00:21
  • 2
    Graham, Knuth, & Patashnik, Concrete Mathematics, has (amongst many other good things) a nice introduction to the rudiments of finite calculus and finite differences. It’s very well-written and amazingly inexpensive for a textbook, and it’s one of the most-used books in my mathematical library. – Brian M. Scott Sep 07 '13 at 05:48
  • 1
    @BrianM.Scott That is probably a better suggestion. Thanks. – Potato Sep 07 '13 at 23:07

2 Answers2

4

Let $a_0,a_1,a_2,a_3,\dots$ be a sequence. Let $b_0,b_1,b_2,b_3,\dots$ be the sequence of (first) differences of the $a_i$. So $b_i=a_{i+1}-a_i$.

In general, if the sequence $b_0,b_1,b_2,\dots$ is given by $b_i=P(i)$, where $P$ is a polynomial of degree $k$, then the original sequence is given by a polynomial of degree $k+1$. This is a result in a large and useful subject called the calculus of finite differences.

It is analogous to the result that if the derivative of a function is a polynomial of degree $k\ge 0$, then the function is a polynomial of degree $k+1$.

Thus, automatically, the sequence of the post is given by a polynomial of degree $3$.

André Nicolas
  • 507,029
3

Not quite an answer but a partial explanation: the equation can be rewritten as $T(n)-T(n-1) = n(n-1)$ (note that the Fibonacci equation can't readily be 'cleared' in this fashion); we know if $p(x)$ is polynomial of degree $n$ then the finite difference $\Delta p(x) \equiv p(x+1)-p(x)$ is polynomial of degree $n-1$ (this isn't too hard to prove using the binomial theorem and makes a nice expression — you should even be able to get an explicit form for the coefficients of $\Delta p(x)$ if you try), so it makes sense to try and 'invert' this and work with the assumption that $T()$ is a third-degree polynomial for the given problem.

In fact, the so-called Bernoulli polynomials give one straightforward approach to solving this problem: they serve to 'invert' the finite-difference operator for monomials $x^n$ (in other words, if $B_{n+1}(x)$ is the order $n+1$ Bernoulli polynomial, then we have $\Delta B_{n+1}(x) = x^n$, up to a small multiplicative factor) in the same way that regular monomials do the same thing for derivatives. Since the finite-difference operator is linear (that is, $\Delta(ap_1(x)+bp_2(x)) = a\Delta p_1(x)+b\Delta p_2(x)$), once we understand how to compute the inverse of the finite-difference operation for each individual term of a polynomial we can compute the inverse on the polynomial as a whole.

Steven Stadnicki
  • 51,746