I am stuck doing the proof by induction of the following equation:
$$ 4 M_n = M_{n+3} + M_{n-1} + M_{n-6} + M_{n-7} $$
$M_n$ is defined by: $$M_n= M_{n-1} + M_{n-3}$$ I've executed the proof for the base case = $11$. Now I am proceeding to prove it for $n=k+1$, but I'm stuck in the middle. I need to prove that my right side yields $4M_{k+1}$ just like the left side. Here's what I have done so far:
\begin{eqnarray*} 4M_{k+1} &=& M_{k+4} + M_{k} + M_{k-5} + M_{k-6} \\ &=& M_{k+4} + M_{k} + M_{k-5} + M_{k-6} +M_{k-7} - M_{k-7} \\ &=& M_{k+4} + M_{k} + M_{k-4} + M_{k-6}- M_{k-7} \\ &=& M_{k+4} + M_{k} + M_{k-3}- M_{k-7} \\ &=& M_{k+4} + M_{k-1}+ M_{k-3} + M_{k-3}- M_{k-7} \\ \end{eqnarray*} I'm at a lost regarding what to be done next. I can't see any ways to subsitute so that I can $4M_{k+1}$ somehow.
In problems like this, the induction step is always completely trivial, in the sense that the proof method does not change from problem to problem. In fact, the inductive step will always hold; the meat of the proof is in the base case, which you have already solved.
You need to show that $$ M_{n+3}-4M_n+M_{n-1}+M_{n-6}+M_{n-7}\stackrel{?}=0\tag{*} $$ holds for all $n$. Assume that it holds for all $k<n$. Expand out all of the summands on the left hand side using $M_{i}=M_{i-1}+M_{i-3}$, and regroup. You get $$ \big(M_{n+2}-4M_{n-1}+M_{n-2}+M_{n-7}+M_{n-8}\big)+\big(M_{n}-4M_{n-3}+M_{n-4}+M_{n-9}+M_{n-10}\big) $$ But by the induction hypothesis, applied to $k=n-1$ and $k=n-3$, both parenthesized sums are zero! Therefore, $(*)$ holds, completing the inductive step.
However, this inductive step required going back three steps, as it used the previous cases $k=n-1$ and $k=n-3$. Therefore, this would require three consecutive base cases, $n=7,8$ and $9$.
Note that there was nothing special about the coefficients in $(*)$ that allowed this proof to work. In fact, here is the inductive step in a proof that $M_{n}=M_{n-1}$: $$ M_n = M_{n-1}+M_{n-3}\stackrel{\text{ind}}=M_{n-2}+M_{n-4}=M_{n-1} $$ Since the equation $M_n=M_{n-1}$ is obviously false, there must be something wrong with the base case.
Finally, one last note above proving problems like this in general. Let $L$ be the "left-shift operator" on sequences. This takes a sequence $A$ and returns a new sequence $LA$, whose terms are $(LA)_n= A_{n+1}$. Your recurrence $M_{n+3}=M_{n+2}+M_{n}$ can be written as $L^3M_n=L^2M_n+M_n$, or more succintly as $$(L^3-L^2-L)M=0.\tag1$$ On the other hand, the recurrence you want to prove is $$(L^{10}-4L^7+L^6+L+1)M=0.\tag2$$ To use $(1)$ to prove $(2)$, simply note that the polynomial $L^3-L^2-L$ divides into the polynomial $L^{10}-4L^7+L^6+L+1$, with quotient $f(L)=-1 - L + L^2 - 2 L^4 + L^5 + L^6 + L^7$, so you can simply apply the operator $f(L)$ to both sides of $(1)$, and $(2)$ will follow.