search
Log In
0 votes
25 views
Prove Theorem $4:$ Let $c_{1},c_{2},\dots,c_{k}$ be real numbers. Suppose that the characteristic equation

$$r^{k}-c_{1}r^{k-1}-\dots c_{k} = 0$$

has $t$ distinct roots $r_{1},r_{2},\dots,r_{t}$ with multiplicities $m_{1},m_{2},\dots,m_{t},$ respectively, so that $m_{i}\geq 1\:\text{for}\: i = 1,2,\dots,t$ and $m_{1} + m_{2} + \dots + m_{t} = k.$ Then a sequence $\{a_{n}\}$ is a solution of the recurrence relation.

$$a_{n} = c_{1}a_{n-1} + c_{2}a_{n-2} + \dots + c_{k}a_{n-k}$$

if and only if

$$a_{n} = (\alpha_{1},0 + \alpha_{1,1n} +  \dots + \alpha_{1,m_{1}-1}n^{m_{1}-1})r_{1}^{n} + (\alpha_{1},0 + \alpha_{2,1}n  \dots \alpha_{1,m_{2}-1}n^{m_{2}-1})r_{2}^{n} +\dots + (\alpha_{t},0 + \alpha_{t,1}n  \dots \alpha_{t,m_{t}-1}n^{m_{t}-1})r_{t}^{n} $$

for $n = 0, 1, 2,\dots,$ where $\alpha_{i,j}$ are constants for $1 \leq i \leq t\:\text{and}\: 0 \leq j \leq m_{i} - 1.$
in Combinatory
edited by
25 views

Please log in or register to answer this question.

Related questions

1 vote
0 answers
1
37 views
Prove Theorem $6:$Suppose that $\{a_{n}\}$ satisfies the liner nonhomogeneous recurrence relation $a_{n} = c_{1}a_{n-1} + c_{2}a_{n-2} + \dots + c_{k}a_{n-k} + F(n),$ where $c_{1}.c_{2},\dots,c_{k}$ ... is $m,$ there is a particular solution of the form $n^{m}(p_{t}n^{t} + p_{t-1}n^{t-1} + \dots + p_{1}n + p_{0})s^{n}.$
asked May 6 in Combinatory Lakshman Patel RJIT 37 views
0 votes
0 answers
2
26 views
Solve the recurrence relation $T (n) = nT^{2}(n/2)$ with initial condition $T (1) = 6$ when $n = 2^{k}$ for some integer $k.$ [Hint: Let $n = 2^{k}$ and then make the substitution $a_{k} = \log T (2^{k})$ to obtain a linear nonhomogeneous recurrence relation.]
asked May 6 in Combinatory Lakshman Patel RJIT 26 views
1 vote
0 answers
3
20 views
It can be shown that Cn, the average number of comparisons made by the quick sort algorithm (described in preamble to question $50$ in exercise $5.4),$ when sorting $n$ ... $48$ to solve the recurrence relation in part $(A)$ to find an explicit formula for $C_{n}.$
asked May 6 in Combinatory Lakshman Patel RJIT 20 views
...