World's most popular travel blog for travel bloggers.

# [Answers] Why is $\sum_{j=1}^{n-1}[\Pi_{k=1}^{j}[(n-k)]]=2^n$?

, ,
Problem Detail:

In CLRS book, in the road cutting example there is a recursion formula

$$1+\sum_{j=0}^{n-1}T(j)$$ and it can be proved that the sum is $$2^n$$

by simple induction. In 3-rd edition it is a formula 15.3 on a page 364.

As I can understand from the recursion-tree aproach, the recursion tree which can be built for the said problem is $$1->(n-1)->(n-2)|each.node->(n-3)|each.node->...$$

and so on, which can be summed as $$\sum_{j=1}^{n-1}[\Pi_{k=1}^{j}[(n-k)]]$$

How can I come up with the suggestion of $2^n$ from this recursion tree (or why this tree is wrong and what can be the right approach to suggesting $2^n$ running time)?

#### Answered By : Rick Decker

Minor nit: your first displayed expression should be $$T(n) = \begin{cases} 1 & \text{if n=0,}\\ 1 + \sum_{j=0}^{n-1}T(j) & \text{otherwise} \end{cases}$$ You can indeed solve this by looking at the recurrence tree, but you don't wind up with your sum of products expression (try it for $n=4$ to see that). For this problem there's an easier way, though:

Hint: What is $T(n+1)-T(n)$?

You can take a look at our reference question, on recurrence relations, as well.