3
$\begingroup$

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

  • 2
    Have you tried splitting the summation into two summations, for $m 2^{j-1}$ and $-j 2^{j-1}$, and solving those separately?2011-09-02

2 Answers 2

6

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?

  • 0
    @Alex Glad to help.2011-09-03
3

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.