[Solved]: Why can any polynomial and exponential be represented as a recurrence?

Problem Detail: 

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

Asked By : Hassan

Answered By : FrankW

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/20119

3.2K people like this

 Download Related Notes/Documents