B(n+2) - B(n+1) = Sum[(k+1)*S(n+1,k+1),{k,0,n}]

B(n+1) = Sum[S(n+1,k+1),{k,0,n}]

B(n+2) - 2*B(n+1) = Sum[(k+1)*S(n+1,k+1),{k,0,n}] - Sum[S(n+1,k+1),{k,0,n}] = Sum[k*S(n+1,k+1),{k,0,n}]

Thanks. The first identity is somewhat non-obvious (to me, at least ;-), but I eventually got to it this way.

1) S(n+2,k+1) = (k+1)*S(n+1,k+1) + S(n+1,k).

2) B(n+2) = Sum[S(n+2,k+1),{k,0,n+1}] = Sum[S(n+2,k+1),{k,0,n}] + 1.

3) B(n+1) = Sum[S(n+1,k),{k,0,n+1}] = Sum[S(n+1,k),{k,0,n}] + 1.

... so that...

4) B(n+2) - B(n+1) = Sum[S(n+2,k+1),{k,0,n}] + 1 - (Sum[S(n+1,k),{k,0,n}] + 1) = Sum[S(n+2,k+1),{k,0,n}] - Sum[S(n+1,k),{k,0,n}] = Sum[(k+1)*S(n+1,k+1) + S(n+1,k),{k,0,n}] - Sum[S(n+1,k),{k,0,n}] = Sum[(k+1)*S(n+1,k+1) + S(n+1,k) - S(n+1,k),{k,0,n}] = Sum[(k+1)*S(n+1,k+1),{k,0,n}].

Do you have a combinatorial explanation?

I don't know of one. It just follows from the definition of Stirling numbers of the second kind and Bell numbers. As can be seen, in some cases S(n,n) = 1 and S(n,0) = 0 are implicitly used also in manipulating the sums. An additional aspect is the changing of indices for the Bell numbers, which affects the sums also. This is the same approach Ioulia Baoulina used.

What do you think about the next combinatorial explanation?

Let order the equality the following way:

B(n+2)=2B(n+1)+Sum[k*Stirling(n+1,k+1),{k,0,n}]

Using the basic combinatorial meaning of Bell and Stirling numbers we show that both side enumerates the same combinatorial objects.

The left hand side is the number of partitions of (n+2).

The right hand side is the same but taking care about the place of a distinguished alement/say the (n+2)th element.

B(n+1): the number of partitions of (n+2) such that the (n+2)th element creates a single block: take simple a partition of (n+1) and add a single block to it including the (n+2)th element.

B(n+1): the number of partitions of (n+2) such that the (n+2)th element is in the block that includes the (n+1)th element: take a partition of (n+1) and add the (n+2)th element into the block that includes the (n+1)th element

Sum[k*Stirling(n+1,k+1),{k,0,n}]: the number of partitions of (n+2) such that the (n+2)th element is not in a single block and (n+2)th and (n+1)the element is not in the same block:

k*Stirling(n+1,k+1): is the number of partitions of (n+1) into (k+1) non-epty block, one block is pointed, but not the one that includes the (n+1)th element: take such a partition and add the (n+2)th element into the pointed block.

So far as I can tell, that works. Nice.

May I ask, what is the pattern you meant in your question?

You could also look at exploring related identities of this type computationally. There's an (old, but useful) Stirling.m package maintained by the RISC combinatorics group at http://www.risc.jku.at/research/combinat/software/ergosum/RISC/Stirling.html which you might find useful, especially since the Bell numbers are expressed as a finite sum of the Stirling numbers of the second kind.

The original sum given in your first post also suggests some ordinary generating function tricks of the trade. Note that expressions for the ordinary generating function of the Bell numbers are given on MathWorld. To arrive at these from your identity, you can perform the sums in the attached image (TeX formatting should be included in these posts ...) An ODE for the exponential generating function of the Bell numbers is setup using the bivariate EGF for the Stirling numbers as well. You also might try seeing what you get by applying summation by parts to the identity.

Benyi Beata, the pattern in my question relates to the appendix in my pre-print "Quasi-Sunflower Sperner Families and Dedekind's Problem", which is listed in my research. Sorry it took me so long to respond, and thank you again for you insights.