What is the recursive formula for the sequence sn?

[Shackleford]

Oddly enough, I don't remember doing a problem like. I have had a problem where I've been given the explicit formula and then asked to use induction to prove that it's correct.

The sequence s_n is defined by the recursion formula

s_{n+1} = \frac{n+1}{2n}s_n, s_1 = 1

Determine a "formula" for (s_n).

I think that I'm supposed to back-substitute s_n into the recursion formula and go from there.

 

[haruspex]

It's not clear to me whether in your present problem you are given the explicit formula and asked to show it is correct, or whether it is the problem as quoted in your post. If the latter, what do you think you are back-substituting in?

 

[Mentallic]

It's not clear to me whether in your present problem you are given the explicit formula and asked to show it is correct, or whether it is the problem as quoted in your post. If the latter, what do you think you are back-substituting in?

The OP is saying that he's solved problems where he's given an explicit formula and used induction to prove it is correct, but hasn't attempted a problem like the one in which he quoted.

At least, that's what I think

Oddly enough, I don't remember doing a problem like. I have had a problem where I've been given the explicit formula and then asked to use induction to prove that it's correct.
I think that I'm supposed to back-substitute s_n into the recursion formula and go from there.

Start by figuring out what s_1,s_2,s_3,s_4 are, but don't substitute the value of s_{n-1} in when figuring out s_n and don't simplify the expression at all. Then start with s_4 and begin by substituting s_3 in, then s_2 etc. Do you notice a pattern?

 

[Shackleford]

The OP is saying that he's solved problems where he's given an explicit formula and used induction to prove it is correct, but hasn't attempted a problem like the one in which he quoted.

At least, that's what I think
Start by figuring out what s_1,s_2,s_3,s_4 are, but don't substitute the value of s_{n-1} in when figuring out s_n and don't simplify the expression at all. Then start with s_4 and begin by substituting s_3 in, then s_2 etc. Do you notice a pattern?

Yes, currently, the full problem is find the explicit formula, prove using induction, and then determine if it converges. I can do the last two parts; I'm just not sure how to get started. I figured that I could list the first few terms in the sequence and try to find a pattern, but I wasn't sure if there was a better, less brute forth method. Heh.

Eh. It looks like \frac{n!}{2n}

 

[Mentallic]

I can't think of any simpler methods for your problem than plugging and finding the pattern, because the pattern is easy to notice.

However, if you have to find an explicit formula for more complicated recurrences, then you should check out generating functions:

http://faculty.tru.ca/smcguinness/M270F11/M270F11notes3.pdf

No, it can't be \frac{n!}{2n} because testing for n=1, we're already given that s_1=1 but \frac{n!}{2n}=\frac{1!}{2\cdot 1}=\frac{1}{2}.

Could you write out what s_2 is in terms of s_1, then s_3 in terms of s_2?

 

[Shackleford]

Oops. You're right. Let me look at it again. I forgot to test for s₁.

 

[Shackleford]

s₁ = 1
s₂ = \frac{2}{2}s₁
s₃ = \frac{3}{4}s₂
s₄ = \frac{4}{6}s₃
s₅ = \frac{5}{8}s₄

 

[Mentallic]

Ok good, but now do it without equating 2*n in the denominator, just leave it as 2*3 for example.

Now, starting at s₄ (you can start at s₅ but s₄ should be far enough up the chain to notice the pattern), begin by substituting the value of s₃ in terms of s₂ so you then have s₄ in terms of s₂. Then substitute again so it's in terms of s₁, all the while not simplifying at all. Do you notice any patterns? Could you figure out what s_n would look like in terms of s₁?

 

[Shackleford]

Ok good, but now do it without equating 2*n in the denominator, just leave it as 2*3 for example.

Now, starting at s₄ (you can start at s₅ but s₄ should be far enough up the chain to notice the pattern), begin by substituting the value of s₃ in terms of s₂ so you then have s₄ in terms of s₂. Then substitute again so it's in terms of s₁, all the while not simplifying at all. Do you notice any patterns? Could you figure out what s_n would look like in terms of s₁?

(s_n) = n(\frac{1}{2})^n-1

 

[Mentallic]

That's it!

 

[haruspex]

Sorry I couldn't get back to this earlier.
Fwiw, there are some more methodical approaches than pattern spotting. On this one, I would first note that it is homogeneous, i.e. Given any two solutions to the recursion formula, any linear combination is also a solution.
Next, look at the asymptotic behaviour of the formula. For large n, it is roughly s_n+1 = s_n/2, suggesting the substitution s_n = u_n2^-n. That yields $\frac{u_{n+1}}{n+1}=\frac{u_n}{n}$.