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

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook