# We have a recursively defined sequence a_{n}. a_{0}=0,a_{1}=3, and a_{n

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.

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

escumantsu
Step 1
Given that: $$\displaystyle{\left\lbrace{a}_{{{n}}}\right\rbrace}$$ be a sequance of defined recursively $$\displaystyle{a}_{{{0}}}={0},\ {a}_{{{1}}}={3}$$
$$\displaystyle{a}_{{{n}}}={3}{a}_{{{n}-{1}}}-{2}{a}_{{{n}-{2}}}$$ for $$\displaystyle{n}\geq{2}$$
To show: $$\displaystyle{a}_{{{n}}}={3}\cdot{2}^{{{n}}}-{3}$$ for $$\displaystyle{n}\geq{2}$$
we will use strong mathematical induction
for $$\displaystyle{n}={0}\ {a}_{{{0}}}={3}\cdot{2}^{{{0}}}-{3}={0}$$
$$\displaystyle{n}={1}\ {a}_{{{1}}}={3}\cdot{2}^{{{1}}}-{3}={3}$$
So, for $$\displaystyle{n}={0},\ {n}={1}$$ it is true
Let us assume it is true for all $$\displaystyle{k}\leq{n}$$
Such that $$\displaystyle{a}_{{{k}}}={3}\cdot{2}^{{{k}}}-{3}\ \forall{k}\leq{n}$$
Now for $$\displaystyle{k}={n}+{1}$$
So, $$\displaystyle{a}_{{{n}+{1}}}={3}{a}_{{{n}}}-{2}{a}_{{{n}-{1}}}$$
$$\displaystyle={3}{\left({3}\cdot{2}^{{{n}}}-{3}\right)}-{2}{\left({3}\cdot{2}^{{{n}-{1}}}-{3}\right)}$$
$$\displaystyle{\left(\because\right.}$$ by induction $$\displaystyle{a}_{{{n}}}={3}\cdot{2}^{{{n}}}-{3},\ {a}_{{{n}-{1}}}={3}\cdot{2}^{{{n}-{1}}}-{3}{)}$$
$$\displaystyle{a}_{{{n}+{1}}}={3}^{{{2}}}\cdot{2}^{{{n}}}-{9}-{6}\cdot{2}^{{{n}-{1}}}+{6}$$
$$\displaystyle={3}\cdot{2}^{{{n}-{1}}}{\left({3}\cdot{2}-{2}\right)}-{3}$$
$$\displaystyle={3}\cdot{2}^{{{n}-{1}}}\cdot{4}-{3}$$
$$\displaystyle={3}\cdot{2}^{{{n}-{1}}}\cdot{2}^{{{2}}}-{3}$$
$$\displaystyle{a}_{{{n}+{1}}}={3}\cdot{2}^{{{n}+{1}}}-{3}$$