Question

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

Discrete math
ANSWERED
asked 2021-08-20
Solve the recursion:
\(\displaystyle{A}_{{{1}}}={1}.\ {A}_{{{2}}}=-{1}\)
\(\displaystyle{A}_{{{k}}}={5}{A}_{{{k}-{1}}}-{6}{A}_{{{k}-{2}}}\)

Expert Answers (1)

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
Answer:
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}}}\)
21
 
Best answer

expert advice

Have a similar question?
We can deal with it in 3 hours

Relevant Questions

asked 2021-07-30
Solve the following recurrence relation:
a) \(\displaystyle{a}_{{{n}+{1}}}={d}{a}_{{{n}}}+{c},\ {a}_{{{0}}}={0}\)
b) \(\displaystyle{{a}_{{{n}+{1}}}^{{{3}}}}={2}{{a}_{{{n}}}^{{{3}}}},\ {a}_{{{0}}}={5}\)
c) \(\displaystyle{F}_{{{n}}}={5}{F}_{{{n}-{1}}}-{6}{F}_{{{n}-{2}}},\ {F}_{{{0}}}={1}\) and \(\displaystyle{F}_{{{1}}}={4}\)
asked 2021-08-15

Example: Partitions of Sets
a. Let \(\displaystyle{A}={\left\lbrace{1},{2},{3},{4},{5},{6}\right\rbrace},{A}_{{{1}}}={\left\lbrace{1},{2}\right\rbrace},{A}_{{{2}}}={\left\lbrace{3},{4}\right\rbrace}\) and \(\displaystyle{A}_{{{3}}}={\left\lbrace{5},{6}\right\rbrace}\). Is \(\displaystyle{\left\lbrace{A}_{{{1}}},{A}_{{{2}}},{A}_{{{3}}}\right\rbrace}\) a partition of A?
b. Let Z be the set of all integers and let:
\(\displaystyle{T}_{{{0}}}={\left\lbrace{n}\in{Z}{\mid}{n}={3}{k},\text{for some integer}\ {k}\right\rbrace}\)
\(\displaystyle{T}_{{{1}}}={\left\lbrace{n}\in{Z}{\mid}{n}={3}{k}+{1},\text{for some integer}\ {k}\right\rbrace}\), and
\(\displaystyle{T}_{{{2}}}={\left\lbrace{n}\in{Z}{\mid}{n}={3}{k}+{2},\text{for some integer}\ {k}\right\rbrace}\)
Is \(\displaystyle{\left\lbrace{T}_{{{0}}},{T}_{{{1}}},{T}_{{{2}}}\right\rbrace}\) a partition of Z?

asked 2021-08-19
Finding a Cartesian Product.
Let \(\displaystyle{A}_{{{1}}}={\left\lbrace{x},{y}\right\rbrace},\ {A}_{{{2}}}={\left\lbrace{1},{2},{3}\right\rbrace},\) and \(\displaystyle{A}_{{{3}}}={\left\lbrace{a},{b}\right\rbrace}.\)
a) Find \(\displaystyle{A}_{{{1}}}\times{A}_{{{2}}}.\)
b) Find \(\displaystyle{A}_{{{1}}}\times{A}_{{{2}}}\times{A}_{{{3}}}.\)
asked 2021-08-16
We have a recursively defined sequence \(\displaystyle{a}_{{{n}}}\).
\(\displaystyle{a}_{{{0}}}={0},{a}_{{{1}}}={3}\), and \(\displaystyle{a}_{{{n}}}={3}{a}_{{{n}-{1}}}-{2}{a}_{{{n}-{2}}}\) for \(\displaystyle{n}\geq{2}\)
We would like to prove that f or all \(\displaystyle{n}\geq{0},{a}_{{{n}}}={3}\cdot{2}^{{{n}}}-{3}\).
Prove this using the stronger mathematical induction.
...