1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Sum help

  1. Jul 10, 2010 #1
    sorry for the many threads

    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
    [tex]S_n=S_{n-1}+S_{n-2} ---S_1+1 [/tex]

    no idea to prove that :
  2. jcsd
  3. Jul 10, 2010 #2


    User Avatar
    Science Advisor
    Homework Helper

    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?
  4. Jul 10, 2010 #3
    I assume that you mean [itex]S_n[/itex] is the number of ways to express [itex]n[/itex] 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 [itex]n[/itex] different cases.

    Explicitly: if the last integer is 1, then the rest of the integers sum to [itex]n-1[/itex]...
  5. Jul 10, 2010 #4
    it means 3 can be written as 1+1+1 , 2+1, 1+2, 3 so 4 different ways..
  6. Jul 10, 2010 #5
    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..

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook