Results 1 to 2 of 2

Math Help - Proof by induction

  1. #1
    Senior Member
    Joined
    Apr 2009
    Posts
    306

    Proof by induction

    Show that for a set the sums of elements in the subsets of can produce any element of the set .
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by usagi_killer View Post
    Show that for a set the sums of elements in the subsets of can produce any element of the set .


    For n= 1 (and for n= 2,3 also) the result is easily checked, so assume the result is true for k up to n-1 and prove for k = n.

    Now, let  1\le m\le \frac{m(m+1)}{2}:

    1) If m\le \frac{(m-1)m}{2} then apply the inductive hypothesis to the subset N:=\{1,2,...,n-1\}\subset\{1,2,...,n\}=\mathbb{S}, otherwise;

    2) k\in \left\{\frac{n(n-1)}{2}+1,\frac{(n-1)n}{2}+2,\ldots,\frac{(n-1)n}{2}+n=\frac{n(n+1)}{2}\right\} , and then it's easy to see that k=1+2+\ldots+(n-1)+k , with 1\le k\le n

    Tonio
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Another proof by induction
    Posted in the Algebra Forum
    Replies: 9
    Last Post: June 9th 2011, 04:06 PM
  2. Proof by induction
    Posted in the Calculus Forum
    Replies: 2
    Last Post: March 12th 2010, 04:01 AM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM
  5. Proof by induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 18th 2007, 07:15 PM

Search Tags


/mathhelpforum @mathhelpforum