Results 1 to 4 of 4
Like Tree3Thanks
  • 2 Post By Plato
  • 1 Post By Plato

Thread: Proof by induction

  1. #1
    Newbie
    Joined
    Nov 2017
    From
    South Asia
    Posts
    2

    Question Proof by induction

    Let A be a set of size n, where n is an integer. Prove by induction that |{x ⊆ A | |x| = 2}| =n(n−1) / 2

    Not sure how to approach this.

    Would i be best assigning n with a value like 2?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Dec 2013
    From
    Colombia
    Posts
    1,822
    Thanks
    592

    Re: Proof by induction

    For the base case, yes.

    For the induction step notice that only one of the $n+1$ elements is "new", so you just add pairs that include that element to the total for the $|A|=n$.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,459
    Thanks
    2728
    Awards
    1

    Re: Proof by induction

    Quote Originally Posted by inayat View Post
    Let A be a set of size n, where n is an integer. Prove by induction that |{x ⊆ A | |x| = 2}| =n(n−1) / 2?
    |{x ⊆ A | |x| = 2}| =n(n−1) / 2 That is the strangest notation I have seen. It took quite a while to come to a reasonable reading.
    Does it mean that given a set of containing n elements then the cardinality of the collection of all subsets of the given set the contain two elements is $\dfrac{n(n-1)}{2}$.

    Lets use some usual notation. $\|A\|=n$, i.e. the set $A$ has $n$ elements then $\|\{x\subseteq A| \|x\|=2\}\|=\dfrac{n(n-1)}{2}$
    Suppose that $n=1$ so $\{x\subseteq A| \|x\|=2\}=\emptyset$, i.e. there can be no two element subsets.
    So note $\dfrac{1(1-1)}{2}=0$ That proved the base case.

    Now suppose $K>1~\&~\|A\|=K$ so that $\|\{x\subseteq A| \|x\|=2\}\|=\dfrac{K(K-1)}{2}$.
    Try to move up to $\|A\|=K+1$
    Last edited by Plato; Nov 10th 2017 at 07:38 PM.
    Thanks from topsquark and inayat
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,459
    Thanks
    2728
    Awards
    1

    Re: Proof by induction

    Quote Originally Posted by inayat View Post
    Let A be a set of size n, where n is an integer. Prove by induction that |{x ⊆ A | |x| = 2}| =n(n−1) / 2
    FROM A PM
    Quote Originally Posted by inayat
    Thanks for the help on the thread i posted.
    Would i be right to sub in K+1 into the original question? Not sure how to proceed.
    This is so puzzling because this is such a well know formula in another context.
    Here is where I left it: the statement is true for the base case $n=1$ Then comes an induction hypothesis, the statement is true for some $K>1$.
    Now the goal is true for that $K+1$.
    So we consider a set $B~\&~\|B\|=K+1$, Here is where the proof js unusual.
    List the set $\{b_1,b_2,\cdots,b_K,b_{K+1}\}$. Remove the last element, $B'=\{b_1,b_2, \cdots,b_K \}$ contains $\dfrac{K(K-1)}{2}$ two-element subsets by the induction hypothesis. Form a new collection of two-element subsets $\mathcal{B}=\{\{b_1,b_{K+1}\},\{b_2,b_{K+1}\}, \cdots,\{b_K,b_{K+1}\}\}$

    Take a moment to convince yourself that $\|\mathcal{B}\|=K$ Let $\mathcal{B}'$ be the collection of all two-elements of \mathcal{B}$

    $ \begin{align*}\|\mathcal{B}'\|&=\|B'\|+K \\&=\dfrac{K(K-1)}{2}+K\\&=\dfrac{K(K-1)+2K}{2}\\&=\dfrac{(K^2+K)}{2}\\&=\dfrac{[K+1]K}{2}\\&=\dfrac{[K+1]([K+1]-1)}{2} \end{align*}$
    QED
    Thanks from inayat
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by induction
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 16th 2013, 04:47 AM
  2. proof by induction
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: May 23rd 2012, 09:06 AM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Mar 8th 2009, 10:33 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Jun 8th 2008, 02:20 PM
  5. Induction Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Feb 25th 2008, 09:01 PM

/mathhelpforum @mathhelpforum