Question

# Solve the recursion: A_{1}=1.\ A_{2}=-1 A_{k}=5A_{k-1}-6A_{k-2}

Discrete math
Solve the recursion:
$$\displaystyle{A}_{{{1}}}={1}.\ {A}_{{{2}}}=-{1}$$
$$\displaystyle{A}_{{{k}}}={5}{A}_{{{k}-{1}}}-{6}{A}_{{{k}-{2}}}$$

2021-08-21
Step 1
Concept Used:
To determine which general solution to use for a recurrence relation of degree 2, determinants can be helpful
from the quadratic equation $$\displaystyle{a}{x}^{{{2}}}+{b}{x}+{c}={0}$$ the discriminant is $$\displaystyle{b}^{{{2}}}-{4}{a}{c}$$
Case 1 if $$\displaystyle{b}^{{{2}}}-{4}{a}{c}{>}{0}$$
we get two distinct roots $$\displaystyle{r}_{{{1}}}$$ and $$\displaystyle{r}_{{{2}}}$$ then general solution is $$\displaystyle{a}_{{{n}}}=\alpha_{{{1}}}{\left({r}_{{{1}}}\right)}^{{{n}}}+\alpha_{{{2}}}{\left({r}_{{{2}}}\right)}^{{{n}}}$$
Case 2 if $$\displaystyle{b}^{{{2}}}-{4}{a}{c}={0}$$
we get one root with multiplicity 2 $$\displaystyle{r}_{{{0}}}$$ then general solution is $$\displaystyle{a}_{{{n}}}=\alpha_{{{1}}}{\left({r}_{{{0}}}\right)}^{{{n}}}+\alpha_{{{2}}}{\left({n}{r}_{{0}}\right\rbrace}{)}^{{{n}}}$$
Step 2
Given:
Given recurrence relation
$$\displaystyle{A}_{{{k}}}={5}{A}_{{{k}-{1}}}-{6}{A}_{{{k}-{2}}},\ {A}_{{{1}}}={1},\ {A}_{{{2}}}=-{1}$$
Solution:
Given $$\displaystyle{A}_{{{k}}}={5}{A}_{{{k}-{1}}}-{6}{A}_{{{k}-{2}}}$$
Therefore characteristic equation is $$\displaystyle{r}^{{{2}}}-{5}{r}+{6}={0}$$
Determinant: $$\displaystyle{b}^{{{2}}}-{4}{a}{c}={\left(-{5}\right)}^{{{2}}}-{4}{\left({1}\right)}{\left({6}\right)}={25}-{24}={1}{>}{0}$$
Since our determinant is greater than 0 we know that we get two distinct real roots
We can factor $$\displaystyle{r}^{{{2}}}-{5}{r}+{6}={0}$$ into $$\displaystyle{\left({r}-{3}\right)}{\left({r}-{2}\right)}={0}$$
So our roots are $$\displaystyle{r}_{{{1}}}={3}$$ and $$\displaystyle{r}_{{{2}}}={2}$$
Hence general solution is $$\displaystyle{A}_{{{k}}}=\alpha_{{{1}}}{\left({3}\right)}^{{{k}}}+\alpha_{{{2}}}{\left({2}\right)}^{{{k}}}$$
Now we find $$\displaystyle\alpha_{{{1}}}$$ and $$\displaystyle\alpha_{{{2}}}$$ by using given initial conditions
Now for $$\displaystyle{A}_{{{1}}}={1}$$
$$\displaystyle{A}_{{{1}}}=\alpha_{{{1}}}{\left({3}\right)}^{{{1}}}+\alpha_{{{2}}}{\left({2}\right)}^{{{1}}}$$
1) $$\displaystyle\Rightarrow{3}\alpha_{{{1}}}+{2}\alpha_{{{2}}}={1}$$
Now for $$\displaystyle{A}_{{{2}}}=-{1}$$
$$\displaystyle{A}_{{{2}}}=\alpha_{{{1}}}{\left({3}\right)}^{{{2}}}+\alpha_{{{2}}}{\left({2}\right)}^{{{2}}}$$
2) $$\displaystyle\Rightarrow{9}\alpha_{{{1}}}+{4}\alpha_{{{2}}}=-{1}$$
By solving equation 1 and 2 we get
$$\displaystyle\neg{\left\lbrace{9}\alpha_{{{1}}}\right\rbrace}+{6}\alpha_{{{2}}}={3}$$
$$\displaystyle{\frac{{-\neg{\left\lbrace{9}\alpha_{{{1}}}\right\rbrace}\pm{4}\alpha_{{{2}}}=\pm{1}}}{{{2}\alpha_{{{2}}}={4}}}}$$
$$\displaystyle\Rightarrow\alpha_{{{2}}}={2}$$
Substitute $$\displaystyle\alpha_{{{2}}}={2}$$ in equation $$\displaystyle{3}\alpha_{{{1}}}+{2}\alpha_{{{2}}}={1}$$ we get
$$\displaystyle{3}\alpha_{{{1}}}+{2}{\left({2}\right)}={1}$$
$$\displaystyle\Rightarrow{3}\alpha_{{{1}}}{1}-{4}$$
$$\displaystyle\Rightarrow\alpha_{{{1}}}={\frac{{-{3}}}{{{3}}}}$$
$$\displaystyle\Rightarrow\alpha_{{{1}}}=-{1}$$
So we get $$\displaystyle\alpha_{{{1}}}=-{1},\ \alpha_{{{2}}}={2}$$
Hence solution of the recursion is
$$\displaystyle{A}_{{{k}}}=-{\left({3}\right)}^{{{k}}}+{2}{\left({2}\right)}^{{{k}}}$$
Step 3
The soluion of the recursion $$\displaystyle{A}_{{{k}}}={5}{A}_{{{k}-{1}}}-{6}{A}_{{{k}-{2}}},\ {A}_{{{1}}}={1},\ {A}_{{{2}}}=-{1}$$ is $$\displaystyle{A}_{{{k}}}=-{\left({3}\right)}^{{{k}}}+{2}{\left({2}\right)}^{{{k}}}$$