# Solve the following recurrence relation: a_{n+1}=da_{n}+c,\ a_{0}=0 and a_{n+1}^{3}=2a_{n}^{3},\ a_{0}=5 and F_{n}=5F_{n-1}-6F_{n-2},\ F_{0}=1

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

## Want to know more about Discrete math?

• Questions are typically answered in as fast as 30 minutes

### Plainmath recommends

• Get a detailed answer even on the hardest topics.
• Ask an expert for a step-by-step guidance to learn to do it yourself.

Nathaniel Kramer

Step 1
According to the given information, it is required to solve the recurrence relation.
a) $$\displaystyle{a}_{{{n}+{1}}}={d}{a}_{{{n}}}+{c},\ {a}_{{{0}}}={0}$$
$$a_{0+1}=a_{1}=da_{0}+c\Rightarrow a_{1}=c$$
$$\displaystyle{a}_{{{1}+{1}}}={a}_{{{2}}}={d}{a}_{{{1}}}+{c}\Rightarrow{a}_{{{2}}}={d}{c}+{c}={\left({d}+{1}\right)}{c}$$
$$\displaystyle{a}_{{{2}+{1}}}={a}_{{{3}}}={d}{a}_{{{2}}}+{c}\Rightarrow{a}_{{{3}}}={d}{\left({d}{c}+{c}\right)}+{c}\Rightarrow{a}_{{{3}}}={d}^{{{2}}}{c}+{d}{c}+{c}={\left({d}^{{{2}}}+{d}+{1}\right)}{c}$$
$$\displaystyle{a}_{{{3}+{1}}}={a}_{{{4}}}={d}{a}_{{{3}}}+{c}\Rightarrow{a}_{{{4}}}={d}{\left({d}^{{{2}}}{c}+{d}{c}+{c}\right)}+{c}\Rightarrow{a}_{{{4}}}={\left({d}^{{{3}}}+{d}^{{{2}}}+{d}+{1}\right)}{c}$$
$$\begin{array}{|c|}\hline a_{n}=(d^{n}+d^{n-1}+d^{n-2}+\cdots+d+1)c \\ \hline \end{array}$$
Step 2
b) $$\displaystyle{{a}_{{{n}+{1}}}^{{{3}}}}={2}{{a}_{{{n}}}^{{{3}}}},\ {a}_{{{0}}}={5}$$
$$\displaystyle{{a}_{{{0}+{1}}}^{{{3}}}}={{a}_{{{1}}}^{{{3}}}}={2}{{a}_{{{0}}}^{{{3}}}}\Rightarrow{{a}_{{{1}}}^{{{3}}}}={2}{\left({5}\right)}^{{{3}}}={2}^{{{1}}}{\left({5}\right)}^{{{3}}}$$
$$\displaystyle{{a}_{{{1}+{1}}}^{{{3}}}}={{a}_{{{2}}}^{{{3}}}}={2}{{a}_{{{1}}}^{{{3}}}}\Rightarrow{{a}_{{{2}}}^{{{3}}}}={2}\times{2}{\left({5}\right)}^{{{3}}}={2}^{{{2}}}{\left({5}\right)}^{{{3}}}$$
$$\displaystyle{{a}_{{{2}+{1}}}^{{{3}}}}={{a}_{{{3}}}^{{{3}}}}={2}{{a}_{{{2}}}^{{{3}}}}\Rightarrow{{a}_{{{3}}}^{{{3}}}}={2}\times{2}\times{2}{\left({5}\right)}^{{{3}}}={2}^{{{3}}}{\left({5}\right)}^{{{3}}}$$
$$\displaystyle{{a}_{{{3}+{1}}}^{{{3}}}}={{a}_{{{4}}}^{{{3}}}}={2}{{a}_{{{3}}}^{{{3}}}}\Rightarrow{{a}_{{{4}}}^{{{3}}}}={2}\times{2}\times{2}\times{2}{\left({5}\right)}^{{{3}}}={2}^{{{4}}}{\left({5}\right)}^{{{3}}}$$
$$\begin{array}{|c|}\hline a_{n}^{3}=2^{n}(5)^{3} \\ \hline \end{array}$$
Step 3
c) $$\displaystyle{F}_{{{n}}}={5}{F}_{{{n}-{1}}}-{6}{F}_{{{n}-{2}}},\ {F}_{{{0}}}={1}$$ and $$\displaystyle{F}_{{{1}}}={4}$$
$$\displaystyle{F}_{{{2}}}={5}{F}_{{{1}}}-{6}{F}_{{{0}}}\Rightarrow{F}_{{{2}}}={5}{\left({4}\right)}-{6}{\left({1}\right)}={14}={2}\times{3}^{{{2}}}-{2}^{{{2}}}$$
$$\displaystyle{F}_{{{3}}}={5}{F}_{{{2}}}-{6}{F}_{{{1}}}\Rightarrow{F}_{{{3}}}={5}{\left({14}\right)}-{6}{\left({4}\right)}={46}={2}\times{3}^{{{3}}}-{2}^{{{3}}}$$
$$\displaystyle{F}_{{{4}}}={5}{F}_{{{3}}}-{6}{F}_{{{2}}}\Rightarrow{F}_{{{4}}}={5}{\left({46}\right)}-{6}{\left({14}\right)}={146}={2}\times{3}^{{{4}}}-{2}^{{{4}}}$$
$$\begin{array}{|c|} \hline F_{n}=2\times3^{n}-2^{n} \\ \hline \end{array}$$

###### Have a similar question?

• Questions are typically answered in as fast as 30 minutes