2
$\begingroup$

I posted this question on math.SE but I haven't got any reply so I'm posting here also.

I am reading The Algorithm Design Manual by Steven S Skiena.

In Section 4.10.1 Recurrence Relations, I understand what a recurrence relation is, but after that following statements have been given:

Any polynomial can be represented by a recurrence, such as the linear function:
$a_n = a_{n-1} + 1, a_1 = 1 \implies a_n = n$

Any exponential can be represented by a recurrence:
$a_n = 2a_{n-1}, a_1 = 1 \implies a_n = 2^{n-1}$

Can anyone explain me the above statements by proving them for any linear function and exponential function, respectively?

EDITED : After help from Raphael and Yuval Filmus , I concluded following prove. Correct me if I am wrong


For any Liner function, General form is $a_n = \alpha n + \beta$
$a_n - a_{n-1} = \alpha n + \beta - (\alpha (n-1) + \beta)$
$a_n - a_{n-1} = \alpha n + \beta - \alpha n + \alpha - \beta$
$a_n - a_{n-1} = \alpha \implies a_n = a_{n-1} +\alpha $
As relation holds in question, $a_n = a_{n-1} + 1 \implies \alpha = 1 $
Now,
$a_{n-1} = a_{n-2} + \alpha , a_{n-2} = a_{n-3} + \alpha , a_{n-3} = a_{n-4} + \alpha , ...$
Therefore, we can expres $a_{n}$ in terms of $a_{n-2}$ and so on
$a_{n} = a_{n-2} + \alpha + \alpha \implies a_{n} = a_{n-2} + 2\alpha $
We can generalize
$a_{n} = \alpha + (n-1)\alpha \implies a_{n} = n\alpha $
As $\alpha = 1 \implies a_{n} = n$
For Exponential, General form is $a_n = cb^n$
$a_n - a_{n-1} = cb^n - cb^{n-1} \implies a_n - a_{n-1} = cb^n - cb^n . b^{-1}$
$a_n - a_{n-1} = cb^n\left(1 - \dfrac{1}{b}\right) $
Substitute $a_n = cb^n$
$a_n - a_{n-1} = a_n\left(1 - \dfrac{1}{b}\right) $
$a_{n-1} = \dfrac{a_n}{b} \implies a_{n} = ba_{n-1} $
As relation holds in question, $a_n = 2a_{n-1} \implies b = 2 $
Now, $a_n = cb^n \implies a_1 = cb^1$
Substitute $a_1 = 1$ and $b=2 \implies c = \dfrac{1}{2}$
Substitute c and b in general form i.e. $a_n = cb^n$
$a_n = \dfrac{1}{2}2^n \implies a_n =2^n2^{-1} \implies a_n = 2^{n-1} $

$\endgroup$

migrated from cstheory.stackexchange.com Jan 30 '14 at 16:36

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 2
    $\begingroup$ What have you tried and where did you get stuck? Just posting an statement and asking for proof is not a good question for SE. (Also, it's a pure mathematics question.) $\endgroup$ – Raphael Jan 30 '14 at 17:36
  • $\begingroup$ The linear case is pretty easy: to get $\alpha n + \beta$, use $a_n = a_{n-1} + \alpha$, or if you want a homogeneous recurrence, $a_n = 2a_{n-1}-a_{n-2}$. $\endgroup$ – Yuval Filmus Jan 30 '14 at 18:52
  • 1
    $\begingroup$ Please don't cross-post on multiple sites. You posted it just 2 days ago on Math.SE; you haven't waited long enough. Second, even if you discovered it would have been better on this site, you should have flagged it on Math.SE to ask the moderators to migrate it, not cross-posted; cross-posting is against site rules. $\endgroup$ – D.W. Jan 31 '14 at 3:12
3
$\begingroup$

The general form for a polynomial is $a_n = \sum_{i=0}^k c_i n^i$. Thus, for $n>0$, we have $$a_n - a_{n-1} = \sum_{i=0}^k c_i n^i - \sum_{i=0}^k c_i (n-1)^i,$$ which can be transformed into the recurrence $$a_n = a_{n-1} + \sum_{i=0}^k c_i n^i - \sum_{i=0}^k c_i (n-1)^i,~~~ a_0 = c_0.$$

For exponentials, the general form is $a_n = c\cdot b^n$. In complete analogy to the example in the book, this is generated by the recurrence $$a_n = b\cdot a_{n-1},~~~ a_0 = c.$$

$\endgroup$
  • 1
    $\begingroup$ How is this better than simply putting $a_n = \sum_{i=0}^k c_in^i$? That is also a recurrence relation. $\endgroup$ – Yuval Filmus Jan 30 '14 at 18:44
  • $\begingroup$ @Yuval It actually uses recurrence. Apparently this is important to the author of the textbook, or he could have written "Any function on the integers can be expressed as a recurrence relation, since $a_n = f(n)$ is a recurrence relation." (I am aware, that every function of the form you gave in your answer can be described by a linear homogenous recurrence relation, but I don't know how to prove this in a way that is easily comprehended by beginners. This is why I opted for the answer I gave.) $\endgroup$ – FrankW Jan 30 '14 at 18:57
  • 1
    $\begingroup$ Your recurrence isn't particularly easy to compute. Usually the recurrence has simple coefficients, indeed often the recurrences considered have constant coefficients. The idea is that using the recurrence simplifies the computation. $\endgroup$ – Yuval Filmus Jan 30 '14 at 19:17
  • $\begingroup$ @Yuval I agree with your first sentence. However, using a recurrence to simplify the computation of a polynomial sounds like a strange idea to me, so I didn't even think about optimizing towards that end. $\endgroup$ – FrankW Jan 30 '14 at 19:53
2
$\begingroup$

Suppose that we are given a polynomial $P$ of degree $d-1$. Consider the following recurrence relation:

$$f(n) = \sum_{k=1}^d (-1)^{k+1} \binom{d}{k} f(n-k).$$

I claim that every polynomial of degree $d-1$ satisfies this recurrence relation; this is shown below. The space of solutions is $d$-dimensional, since we can set (for example) $f(1),\ldots,f(d)$ in any way we want. Since there are also $d$ degrees of freedom for $P$, we conclude that by setting the initial values $f(1),\ldots,f(d)=P(1),\ldots,P(d)$, we get $f(n) = P(n)$ for all $n$.

For example, if $P(n) = \alpha n + \beta$ then the resulting recurrence is $f(n) = 2f(n-1) - f(n-2)$ with initial values $P(1) = \alpha + \beta$ and $P(2) = 2\alpha + \beta$.


We now prove that every polynomial of degree $d-1$ satisfies the recurrence stated above. Since the recurrence is homogeneous, it is enough to show that for $0 \leq t \leq d-1$,

$$ \sum_{k=0}^d (-1)^k \binom{d}{k} (n-k)^t = 0. $$

Opening up the binomial, we get

$$ \sum_{k=0}^d (-1)^k \binom{d}{k} \sum_{\ell=0}^t (-1)^\ell \binom{t}{\ell} n^{t-\ell} k^\ell = 0. $$

It is thus enough to show that for $0\leq\ell\leq d-1$,

$$ \sum_{k=0}^d (-1)^k \binom{d}{k} k^\ell = 0. $$

The linear span of $k^0,\ldots,k^{d-1}$ is spanned by the "falling powers" $1,k,k(k-1),\ldots,k(k-1)\cdots(k-d)$. So it is enough to show that for $0\leq\ell\leq d-1$,

$$ \sum_{k=0}^d (-1)^k \binom{d}{k} k(k-1)\cdots(k-\ell+1) = 0. $$

This quantity is equal to

$$ d(d-1)\cdots(d-\ell+1) \sum_{k=\ell}^d (-1)^k \binom{d-\ell}{k-\ell} = d\cdots(d-\ell+1) (1-1)^{d-\ell} = 0, $$

using the binomial theorem.


Exponentials are easier, as demonstrated by FrankW's answer.


The functions expressible using recurrence relations with constant coefficients are all of the following form: for some $n_0$ and all $n \geq n_0$, $$ f(n) = \sum_i P_i(n) \lambda_i^n, $$ where $\lambda_i$ are arbitrary complex numbers and $P_i$ are arbitrary complex polynomials. The proof uses Jordan canonical form. Above we have seen two special cases of the converse. Here's a question for you to ponder: can any function of this form be realized by a recurrence relation?

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