How to Inductively Prove a Recursive Sequence Formula?

[NuPowerbook]

I have the series 2, 2, 6, 10, 22, 42, 86, 170, 342, 682 which follows the following:

M(1)=2
M(2)=2
M(3)=M(1)+M(2)+2
M(4)=M(3)+M(2)+M(1)
M(5)=M(4)+M(3)+M(2)+M(1)+2
M(6)=M(5)+M(4)+M(3)+M(2)+M(1)

Each value for M(N) for N >= 3 is the sum of all previous values, and add 2 if N is odd.

I found that these two functions describe the sum:
\mbox{If N is odd: }\frac{2^{n+1}+2}{3}
\mbox{If N is even: }\frac{2^{n+1}-2}{3}

Can anyone help me inductively prove this?

EDIT: I guess I tried to represent it as a function and failed. If someone can represent this as a summation for me, then I could probably figure out the inductive proof. I guess my whole problem was I tried to represent it as a recursive function, and since the function was wrong, I could not prove it.

 

[StatusX]

A proof by induction is done as follows. Show the case is true for the first term, n=1. This should be easy, just plug in and verify. Then you need to show that given the expression is true for all terms before the nth term, show that it then must be true for the nth term. In this case, assume the sum expression of the first n-1 terms is accurate, then show that adding the nth term will give the same result as the sum expression evaluated at n.

 

[NuPowerbook]

A proof by induction is done as follows. Show the case is true for the first term, n=1. This should be easy, just plug in and verify. Then you need to show that given the expression is true for all terms before the nth term, show that it then must be true for the nth term. In this case, assume the sum expression of the first n-1 terms is accurate, then show that adding the nth term will give the same result as the sum expression evaluated at n.

I know how to do an inductive proof, but I am just not sure how to prove this. I've never done an inductive proof on a piecewise function where the proof depends on whether the nth term is even or odd.

 

[StatusX]

OK, the way I would do it is to use the sum formulas to generate a pair of equations for M(n) if n is even or odd. For example, if n is odd, subtract the even sum expression for n-1 from the odd expression for n. Then prove by induction that these satisfy the generating equation. Remember, if n is odd, n-1 is even and n-2 is odd.

Edit: wait, those expressions are for M(n). Why did you call them the sum? In any case, that just makes your job easier.

second edit: that formula only matches the generating equation for the first few terms (up to 10). 10+6+2 != 22. no wonder you had a hard time proving it.

 

[NuPowerbook]

OK, the way I would do it is to use the sum formulas to generate a pair of equations for M(n) if n is even or odd. For example, if n is odd, subtract the even sum expression for n-1 from the odd expression for n. Then prove by induction that these satisfy the generating equation. Remember, if n is odd, n-1 is even and n-2 is odd.

Edit: wait, those expressions are for M(n). Why did you call them the sum? In any case, that just makes your job easier.

second edit: that formula only matches the generating equation for the first few terms (up to 10). 10+6+2 != 22. no wonder you had a hard time proving it.

Oh bah, I messed up the formula. It should be correct now.

 

[StatusX]

Take M(6)-M(5). This should show you a pattern you can use to get two expressions for M(n)-M(n-1), one for even n and one for odd n. Prove this relation holds for your formulas as well.

Also, the equation you're looking for is:

M(n) = \left\{\begin{array}{cc}\sum_{k=1}^{n-1} M(k), &\mbox{n even}\\ 2+\sum_{k=1}^{n-1} M(k), &\mbox{n odd}\end{array}