0

$M(n)=3M(n−1)+1$ with base case of $M(1)=1$

Somehow I'm not understanding how to solve the recurrences.

This problem is from my textbook and I was fine until I see this in example. I know it goes like: $M(1)=3\times M(0)+1=1$

$M(2)=3\times 1+1=4$

$M(3)=3\times 4+1=13$

Can I have some hints?

Michael Grant
  • 19,450
Minjae
  • 207

3 Answers3

1

For large enough $n$, $$ M(n)=3M(n-1)+1\\ M(n)=3(3M(n-2)+1)+1\\ M(n)=9M(n-2)+4\\ M(n)=9(3M(n-3)+1)+4\\ M(n)=27M(n-3)+13\\ M(n)=27(3M(n-4)+1)+13\\ M(n)=81M(n-4)+40\\ M(n)=81(3M(n-5)+1)+40\\ M(n)=243M(n-5)+121\\ $$ Keep going until you notice a pattern.

Eventually you will realize that $M(n)=3^{n-1}M(1)+\frac{3^{n-1}-1}{2}=\frac{3^n-1}{2}$.

You can prove this by induction:

The base case is true: $M(1)=\frac{3^1-1}{2}=1$

Now suppose $M(n)=\frac{3^n-1}{2}$. Then $M(n+1)=3M(n)+1=3*\frac{3^n-1}{2}+1=\frac{3^{n+1}-3}{2}+1=\frac{3^{n+1}-1}{2}$. Thus we have proven that $M(n)=\frac{3^n-1}{2}$.

n55
  • 1,563
  • Is there any tip on noticing the pattern easier? Even sometimes I've noticed the pattern, I can't turn it into such a form that is different from the original one which is $M(n)=3M(n−1)+1$ – Minjae Jul 07 '15 at 04:51
  • I would just write it out like I did above, $M(n)$ in terms of $M(n-1)$, then $M(n-2)$, then $M(n-3)$, then $M(n-4)$, and so on, and see if you notice a pattern. For example, the number that is being multiplied to $M(n-i)$ is clearly a power of $3$, but the $1$, $4$, $13$, $40$, $121$ sequence might require more insight. https://oeis.org/A003462 might help. – n55 Jul 07 '15 at 04:58
  • 1
    @Minjae: It’s easier if you don’t carry out the computations along the way, so that you have $3^2M(n-2)+3+1$, $3^3M(n-3)+3^2+3+1$, $3^4M(n-4)+3^3+3^2+3+1$, and so on. Then it’s pretty clear that the general form is $$3^kM(n-k)+\sum_{\ell=0}^{k-1}3^\ell;.$$ Now substitute $k=n-1$ to find that $$M(n)=3^{n-1}M(1)+\sum_{\ell=0}^{n-2}3^\ell=\sum_{\ell=0}^{n-1}3^\ell;,$$ and use the formula for the sum of a geometric series. – Brian M. Scott Jul 07 '15 at 23:07
1

taking two consecutive terms: $$ M(n)=3M(n−1)+1 \\ M(n+1)=3M(n)+1 $$ and subtracting: $$ M(n+1) -M(n) = 3(M(n)-M(n-1)) $$ so $$ M(n+1) - M(n) = 3^{n-1}(M(2)-M(1)) = 3^n $$ similarly: $$ M(n)-M(n-1) = 3^{n-1} $$ adding all such equations: $$ M(n+1) -M(1)= \sum_{k=1}^n 3^k $$ i.e. $$ M(n+1) = \sum_{k=0}^n 3^k = \frac{3^n -1}2 $$

David Holden
  • 18,040
1

You can divide both members by $3^n$ to get $\frac{M(n)}{3^n}=\frac{M(n-1)}{3^{n-1}}+\frac{1}{3^n}$. Let $N(n)=\frac{M(n)}{3^n}$. Thus we have $N(n)-N(n-1)=\frac{1}{3^n}$. It follows that

$$N(n)-N(1)=\sum_{j=1}^{n-1}(N(j+1)-N(j))=\sum_{j=1}^{n-1}\frac{1}{3^{j+1}}.$$

So, $N(n)=\sum_{j=0}^{n-1}\frac{1}{3^{j+1}}$ and $M(n)=\frac{3^n-1}{2}.$

Euler88 ...
  • 2,090