# Homework Help: Help with an inductive proof

1. Feb 12, 2005

### 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.

Last edited: Feb 12, 2005
2. Feb 12, 2005

### 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.

3. Feb 12, 2005

### NuPowerbook

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.

4. Feb 12, 2005

### 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.

Last edited: Feb 12, 2005
5. Feb 12, 2005

### NuPowerbook

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

6. Feb 12, 2005

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

Last edited: Feb 12, 2005
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook