How to Inductively Prove a Recursive Sequence Formula?

  • Thread starter Thread starter NuPowerbook
  • Start date Start date
  • Tags Tags
    Proof
AI Thread Summary
The recursive sequence defined by M(N) has specific rules for odd and even indices, where M(N) for N >= 3 is the sum of all previous terms, with an additional 2 if N is odd. The proposed formulas for M(N) are \(\frac{2^{n+1}+2}{3}\) for odd N and \(\frac{2^{n+1}-2}{3}\) for even N, but they only match the sequence for the first few terms. To prove these formulas inductively, one should establish the base case for n=1 and then show that if the formulas hold for all terms up to n-1, they also hold for n. A suggested approach is to derive two equations for M(n) based on whether n is even or odd and prove the relationship between M(n) and M(n-1). The final equation for M(n) can be expressed as a summation that distinguishes between even and odd cases.
NuPowerbook
Messages
8
Reaction score
0
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:
Physics news on Phys.org
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.
 
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.
 
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:
I multiplied the values first without the error limit. Got 19.38. rounded it off to 2 significant figures since the given data has 2 significant figures. So = 19. For error I used the above formula. It comes out about 1.48. Now my question is. Should I write the answer as 19±1.5 (rounding 1.48 to 2 significant figures) OR should I write it as 19±1. So in short, should the error have same number of significant figures as the mean value or should it have the same number of decimal places as...
Thread 'A cylinder connected to a hanging mass'
Let's declare that for the cylinder, mass = M = 10 kg Radius = R = 4 m For the wall and the floor, Friction coeff = ##\mu## = 0.5 For the hanging mass, mass = m = 11 kg First, we divide the force according to their respective plane (x and y thing, correct me if I'm wrong) and according to which, cylinder or the hanging mass, they're working on. Force on the hanging mass $$mg - T = ma$$ Force(Cylinder) on y $$N_f + f_w - Mg = 0$$ Force(Cylinder) on x $$T + f_f - N_w = Ma$$ There's also...
Back
Top