0

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?

SteveRodgers43
  • 217
  • 1
    Usually, the best thing to do in this situation is to fix $k$ and go through it line by line. You know the claim is true for $k=1$, right (you seem to switch between $m,k$ so I'm not sure). Now, try for $k=2$. Go though your computation to see where your error occirs. – lulu Dec 29 '23 at 03:27
  • $-2^k+2^k = 0\neq 2^{k+1}$ – JMoravitz Dec 29 '23 at 03:27
  • Though, really, isn't it easier to just pull out the multiplicative factor of $3^{m-1}$ and then use the closed form for the geometric sum of $\sum \left(\frac 23\right)^i$? – lulu Dec 29 '23 at 03:28
  • 1
    When you went from $\sum\limits_{i=0}^k3^{\color{red}{k-i}}2^i$ to $\sum\limits_{i=0}^{k-1}(\cdots)+(\text{last term})$, the summands should not have changed appearance. You somehow replaced the exponent in the $3$ there. It should have been $\sum\limits_{i=0}^{k-1}3^{\color{red}{k-i}}2^i + 3^02^k$ which you can factor a $3$ out of. The very final punchline needed should be that $2=3-1$ – JMoravitz Dec 29 '23 at 03:30
  • $3^0 - 2^0 \ne 1$ – jjagmath Dec 29 '23 at 04:04
  • Thank you Lulu and Jmoravitz. I tried using k+1 and checking values and I got 3=5. Then I checked the summands and corrected them. $\sum_{i=0}^{k} 3^{k-i}2^{i} = \sum_{i=0}^{k-1} 3^{k-1}2^{i} + 3^02^k =3\sum_{i=0}^{k-1} 3^{k-1-i}2^{i} + 3^02^k= 3(3^k - 2^k) + 2^k = 3^{k+1} - 3*2^{k}+2^k = 3^{k+1} - 2^{k+1}$ – SteveRodgers43 Dec 29 '23 at 04:05
  • 1
    If you are interested, an extension of this problem is $\sum 2^{a}3^{b}4^{c}=\frac{1}{2}\left[4^{m}-2\cdot 3^{m}+2^{m}\right]$ where the summation is over all possible integer solutions of $a+b+c=m-2$ – acat3 Dec 29 '23 at 04:51

1 Answers1

2

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

acat3
  • 11,897