Never seen this type of recurrence relation before. I need to prove it using induction.
\begin{aligned}u_{1}=3,u_{2}=5,u_{n}=3u_{n-1}-2u_{n-2},n\in \mathbb{N} ,n\geq 3. \end{aligned}
Prove $u_{n} = 2^k+1$
This is what I did:
Basis step
\begin{aligned} P\left( 3\right) :3\cdot 5-2\cdot 3=9\\ \end{aligned}
Inductive step
\begin{aligned} P\left( k\right) :3u_{k-1}-2u_{k-2}=2^{k}+1\\ P\left( k+1\right) :3u_{k}-2u_{k-1}=2^{k+1}+1 \end{aligned}
If I replace $u_{k}$ in $3u_{k}$, still need to solve $2u_{k-1}$
Two questions:
- How can I use my hypothesis to prove $P(k + 1)$ ?
- What's the name of this type of relation where it depends on two previous results?
Would appreciate any help
Your base case should be:
$u_1 = 3 = 2^1+1\\u_2 = 5 = 2^2+1$
In your inductive step you then assume that $u_k = 2^k+1$ and $u_{k-1} = 2^{k-1}+1$ and you need to show that with this assumption then $u_{k+1} = 2^{k+1}+1$.
You know that
$u_{k+1} = 3u_k - 2u_{k-1} = 3(2^k+1) - 2(2^{k-1}+1)$
so you just have to simplify the expression on the right hand side.