• Support PF! Buy your school textbooks, materials and every day products via PF Here!

Help with an inductive proof

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:
[tex]\mbox{If N is odd: }\frac{2^{n+1}+2}{3}[/tex]
[tex]\mbox{If N is even: }\frac{2^{n+1}-2}{3}[/tex]

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:

StatusX

Homework Helper
2,563
1
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.
 
StatusX said:
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

Homework Helper
2,563
1
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:
StatusX said:
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

Homework Helper
2,563
1
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:

[tex] 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} [/tex]
 
Last edited:

Related Threads for: Help with an inductive proof

  • Posted
Replies
4
Views
1K
  • Posted
Replies
3
Views
4K
  • Posted
Replies
0
Views
893
  • Posted
Replies
3
Views
1K
Replies
6
Views
1K
Replies
5
Views
512
Replies
0
Views
2K
Replies
1
Views
1K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top