# Sum help

1. Jul 10, 2010

### dr hannibal

Let S_n denote the number of ways of expressing n as positive integrs..
S_1=1 , s_2=2, s_3=4 ..

Prove that
$$S_n=S_{n-1}+S_{n-2} ---S_1+1$$

no idea to prove that :

2. Jul 10, 2010

### nicksauce

Sorry, but to me it's not clear what your question means. What does it mean to express a positive integer as positive integers? I can only think of one way to express 3 as a positive integer, namely by 3. Can you show how S_3 = 4?

Your notation in the equation is also confusing. What is the meaning of three consecutive minus signs?

3. Jul 10, 2010

### tmccullough

I assume that you mean $S_n$ is the number of ways to express $n$ as a sum of positive integers, where orders matters.

Consider the different cases for the last integer in the sum, all of which are disjoint, since order matters. There are $n$ different cases.

Explicitly: if the last integer is 1, then the rest of the integers sum to $n-1$...

4. Jul 10, 2010

### dr hannibal

it means 3 can be written as 1+1+1 , 2+1, 1+2, 3 so 4 different ways..

5. Jul 10, 2010

### dr hannibal

Yup thats what I meant
for your hint how would I use notation to represent it ..just one line would be enough

c, its just I have been grappling with this question for far too long and have not made any headway..

Thanks