Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$$f(m)=\sum^m_{j=1}(m-j)2^{j-1}$$ I've to understand what is a simple form of $f$ by computing some value of it, but I can't see a simple form of it, can anyone help me? I have also to give a combinatorally and inductive proof of the equality; with the inductive I think I won't have problems, but I'm not so good with the combinatorally proof, can any of you help me, please?

ok I got it, $f(m)=2^m-m-1$. Now I have to count the elements of a certain set in 2 ways to prove the equality, but I don't have any idea.

share|improve this question
2  
Have you tried splitting the summation into two summations, for $m 2^{j-1}$ and $-j 2^{j-1}$, and solving those separately? –  TMM Sep 2 '11 at 1:01
add comment

2 Answers 2

up vote 6 down vote accepted

HINT You are asked to find a combinatorial (or, bijective) proof of the identity $$ 2^{m}-m-1 = \sum_{j=1}^m (m-j) 2^{j-1} .$$

The left hand side counts the number of sets subsets of $\{ 1,2, \ldots, m \}$ with at least $\ldots$ elements. (Fill in the blank.)

Let us count the same thing in another way. Let $S$ be the set that we are trying to pick. Suppose that the second largest element of $S$ is $j$. Then,

  • How many elements of $S$ are strictly larger than $j$? In how many ways can you pick those elements?

  • We also need to pick the elements of $S$ that are strictly smaller than $j$. In how many ways can you do this?

share|improve this answer
    
It probably helps to point out that in this argument we’re choosing $S$ from the set $\{1,2,\dots,m\}$. –  Brian M. Scott Sep 2 '11 at 3:40
    
@Brian Oh, of course. Thanks for pointing it out. –  Srivatsan Sep 2 '11 at 3:43
    
@ Srivatsan: Thanks, it helped. –  Alex M Sep 3 '11 at 0:34
    
@Alex Glad to help. –  Srivatsan Sep 3 '11 at 0:37
add comment

If you compute the first terms, you get

0, 1, 4, 11, 26, 57, 120, 247, 502, 1013

and you look for that in the OEIS, you get to this page which informs you that the sequence is the sequence of Eulerian numbers, gives you various formulas for the numbers and lots of references where you will find more information.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.