I put something into wolfram alpha and I saw that it simplified really well. I wanted to try and prove it, but my attempt is leaving me short a 3. Where am I going wrong?
$\sum_{i=0}^{m-1} 3^{m-1-i}2^{i} = 3^m - 2^m$
Base case: m = 1
$\sum_{i=0}^{0} 3^{1-1-0}2^{0} = 1$
$3^m - 2^m = 3^1 - 2^1 = 1$
Then we have our ind. hyp.
$\sum_{i=0}^{k-1} 3^{k-1-i}2^{i} = 3^k - 2^k$
Now to prove for k + 1
$\sum_{i=0}^{k} 3^{k-i}2^{i} = \sum_{i=0}^{k-1} 3^{k-1-i}2^{i} + 3^02^k = 3^k - 2^k + 2^k = 3^k + 2^{k+1}$
Which does not prove our hypothesis. Can someone help?
In your answer, you have the summand $3^{m-i}2^{i}$ on the LHS but $3^{m-1-i}2^{i}$ on the RHS.
$$ \begin{aligned} \sum_{i=0}^{m}3^{m-i}\cdot 2^{i} &= 3\cdot\sum_{i=0}^{m-1}3^{m-1-i}\cdot 2^{i} + 2^{m} \\ &=3\cdot\left(3^{m}-2^{m}\right) + 2^{m} \\ &= 3^{m+1}-2^{m+1} \end{aligned} $$