I have the recurrence relation:
$2a_n = 7a_{n-1}-3a_{n-2}$ for $a_0=1$ and $a_1=1$,
which I have already solved for:
$2a_n = \frac 25(3)^n + \frac 85(\frac 12)^n$
Then, I am trying to prove that $(\frac 25(3)^n + \frac 85(\frac 12)^n)$ satisfies $(7a_{n-1}-3a_{n-2})$, presumably for all $n$.
$\mathit Basis:$
$2a_0 = \frac 25(3)^0 + \frac 85(\frac 12)^0 = (\frac 25 + \frac 85)/2 = 1 = a_0✓$
$2a_1 = \frac 25(3)^1 + \frac 85(\frac 12)^1 = (\frac {12}{10} + \frac {8}{10})/2 = 1 = a_1✓$
$\mathit Hypothesis:$
For some number $k$ such that $k = n$:
$2a_k = \frac 25(3)^k + \frac 85(\frac 12)^k$
$2a_k = 7a_{k-1}−3a_{k−2}$
$\mathit Induction:$
$2a_{k+1} = 7a_k-3a_{k-1}$
$\frac 25(3)^{k+1} + \frac 85(\frac 12)^{k+1} = 7(\frac {\frac 25(3)^k + \frac 85(\frac 12)^k}2) - 3(\frac {\frac 25(3)^{k-1} + \frac 85(\frac 12)^{k-1}}2)$
$\frac45(3)^{k+1}+\frac{16}{5}(\frac12)^{k+1}=7(\frac25(3)^k+\frac85(\frac12)^k)-3(\frac25(3)^{k-1}+\frac85(\frac12)^{k-1})$
$\frac45(3)^{k+1}+\frac{16}{5}(\frac12)^{k+1}=\frac{14}{5}(3)^k+\frac{56}{5}(\frac12)^k-\frac65(3)^{k-1}-\frac{24}{5}(\frac12)^{k-1}$
$4(3)^{k+1}+16(\frac12)^{k+1}=14(3)^k+56(\frac12)^k-6(3)^{k-1}-24(\frac12)^{k-1}$
$\mathbf{10(3)^{k-1}+40(\frac12)^{k-1}=10(3)^k+40(\frac12)^k}$
This obviously doesn't seem right, but I don't know what I've done wrong. Possibilities I can think of:
- I misinterpreted the instructions and "satisfies" doesn't mean "equals."
- I should be using an inequality statement instead of an equality statement (is this related to the base cases for the relation?).
- I shouldn't have substituted the left-hand $2a_{k+1}$.
- There was an opportunity to expand terms and simplify that I missed (at the beginning? There's a similar question here, but I don't understand how they combined $a^k$ and $a^{k-1}$ terms in their solution).
Any direction is appreciated, thank you.
You should normally do the left & right hand sides separately when trying to prove some relation (e.g., equality in this case) exists between $2$ expressions. Nonetheless, in your case, you get at your second last line
$$4(3)^{k+1}+16(\frac12)^{k+1}=14(3)^k+56(\frac12)^k-6(3)^{k-1}-24(\frac12)^{k-1} \tag{1}\label{eq1A}$$
It seems you made some mistakes getting to your last line.
To compare the $2$ sides, you need to have them both be represented the same way. I will have the power of $3$ and $\frac{1}{2}$ terms be to the power of $k$. The right hand side then becomes, by taking a factor of $3$ and $\frac{1}{2}$ out from the terms,
$$4(3)(3)^k + 16\left(\frac{1}{2}\right)\left(\frac{1}{2}\right)^k = 12(3)^k + 8\left(\frac{1}{2}\right)^k \tag{2}\label{eq2A}$$
Note $a^{k-1} = \left(\frac{a}{a}\right)\left(a^{k-1}\right) = \frac{a^k}{a}$. Using this idea, on the left hand side, by adding a factor of $3$ into $(3)^{k-1}$ (so divide by it in the coefficient to not change the equation value) and a factor of $\frac{1}{2}$ into $\left(\frac{1}{2}\right)^{k-1}$ (likewise divide the coefficient by $\frac{1}{2}$, i.e., multiply by $2$), you get
$$\begin{equation}\begin{aligned} & 14(3)^k + 56\left(\frac{1}{2}\right)^k - 6\left(\frac{1}{3}\right)(3)^k - 24(2)\left(\frac{1}{2}\right)^k \\ & = 14(3)^k + 56\left(\frac{1}{2}\right)^k - 2(3)^k - 48\left(\frac{1}{2}\right)^k \\ & = 12(3)^k + 8\left(\frac{1}{2}\right)^k \end{aligned}\end{equation}\tag{3}\label{eq3A}$$
As you can see, the left & right hand side match, completing your induction procedure.
You may prefer, and find it simpler, to have the terms using $3$ and $\frac{1}{2}$ to the power of $k-1$ instead. If so, you would have got that both sides are
$$12(3)(3)^{k-1} + 8\left(\frac{1}{2}\right)\left(\frac{1}{2}\right)^{k-1} = 36(3)^{k-1} + 4\left(\frac{1}{2}\right)^{k-1} \tag{4}\label{eq4A}$$
and still reached the same conclusion that the induction procedure works. I'll leave it to you if you wish to try confirming that \eqref{eq4A} is what you'll get in that case.