$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?
On
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 $$
On
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}.$
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}$.