Results 1 to 2 of 2

Math Help - What does 3^n count?

  1. #1
    Junior Member
    Joined
    Feb 2010
    From
    New Jersey
    Posts
    73

    What does 3^n count?

    I am asked to prove, combinatorially:

    2 \cdot 3^0+2 \cdot 3^1+2 \cdot 3^2+\ldots+ 2 \cdot 3^{n-1}=3^n-1

    Are they kidding about this? It took me less than half a minute to prove it by factoring out the 2 and using the geometric series.

    The book has an example which says:
    2^0+2^1+2^2+\ldots+ 2^{n-1}=2^n-1

    RHS is the number of non-empty subsets of an n-element set.
    LHS is the number of subsets of n-element subset whose largest element is 1 \le j \le n, summed up.


    So here's the best I could come up with: 3^n is the number of n-digit words you can create from 3 elements with replacement, minus 1. Let's call it all n-digit words, not all zeros, from 3 elements.

    But I can't do the LHS. So far, I figure that, since the n on the RHS stands for word length, I feel like the exponent on LHS might represent the length, too. But 2 times 3^0=2 is not exactly the number of ways ways a one-digit word can be created given three choices (that would be three).

    Any help?
    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    So, we are counting words made of {0, 1, 2}. Then 2\cdot 3^{j-1} is the number of words that have 1 or 2 in the position j and 0 in the positions j+1,\dots,n (positions are counted from 1).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. triangular count
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 27th 2010, 07:22 AM
  2. How to count binary relations?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 3rd 2009, 04:29 PM
  3. Learning to count!
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 14th 2009, 04:02 AM
  4. How to count?
    Posted in the Math Challenge Problems Forum
    Replies: 3
    Last Post: October 7th 2008, 05:17 AM
  5. Using MergeSort to count Inversions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 17th 2007, 04:18 PM

Search Tags


/mathhelpforum @mathhelpforum