# Sequence recursion formula

1. Sep 14, 2014

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

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

2. Sep 15, 2014

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

3. Sep 15, 2014

### Mentallic

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?

4. Sep 15, 2014

### Shackleford

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

Last edited: Sep 15, 2014
5. Sep 15, 2014

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

6. Sep 15, 2014

### Shackleford

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

7. Sep 15, 2014

### Shackleford

s1 = 1
s2 = $\frac{2}{2}$s1
s3 = $\frac{3}{4}$s2
s4 = $\frac{4}{6}$s3
s5 = $\frac{5}{8}$s4

8. Sep 15, 2014

### 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 s4 (you can start at s5 but s4 should be far enough up the chain to notice the pattern), begin by substituting the value of s3 in terms of s2 so you then have s4 in terms of s2. Then substitute again so it's in terms of s1, all the while not simplifying at all. Do you notice any patterns? Could you figure out what sn would look like in terms of s1?

9. Sep 15, 2014

### Shackleford

(sn) = $n(\frac{1}{2})$n-1

10. Sep 16, 2014

### Mentallic

That's it!

11. Sep 16, 2014

### 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 sn+1 = sn/2, suggesting the substitution sn = un2-n. That yields $\frac{u_{n+1}}{n+1}=\frac{u_n}{n}$.