1

This is my work so far:

  • $D(n)$ is the number of ways the set $\{1,2,3,\ldots,n\}$ can be partitioned into two sets.
  • $D(n-1)$ is the number of ways the set $\{1,2,3,\ldots,n-1\}$ can be partitioned into two sets.

$n-1$ can be divided into two sets, say, $A$ and $B$. Now we add element $n$ into $A$ and $B$.

Now each partition of $D(n-1)$ gives two partitions of $D(n)$:

$$D(n) = 2D(n-1)$$

  • To solve:

let $D(n) = r^n$

$r^n = 2r^{n-1}$

$r = 2$

$D(n) = 2Rn$

Is my logic correct?

Robert Miller
  • 317
  • 2
    Questions: (1) What is the $R$ in the expression for $D(n) = 2Rn$? A typo? (2) Have you verified your formula for, say, $n=2$?. – Fabio Somenzi Apr 10 '17 at 01:01

2 Answers2

1

This is not solved by way of a recurrence relation, but here it is anyway.

There are $n\choose{1}$ ways to separate out a one element partition.

There are $n\choose{2}$ ways to separate out a two element partition.

We know that

$$\sum_{k=0}^n {n\choose{k}}=2^n$$

but we want half of

$$\sum_{k=1}^{n-1} {n\choose{k}}=2^n-2$$

so

$$D(n)=2^{n-1}-1$$

Once we see the equation for $D(n)$ we easily see that

$$D(n+1)=2D(n)+1$$

so we have the recurrence relation.

John Wayland Bales
  • 21,814
1

The recurrence will be $$D(n)=2D(n-1)+1$$,because inside each of the D(n-1) ways we can add the $n^{th}$ element in one of the two sets (inside each way) + one way containing {1,2,.......,n-1},{n}. The base case will be $$D(2)=1$$ On Solving this recurrence $$D(n)=2(2D(n-2)+1)+1=2^2D(n-2)+2+1=2^3D(n-3)+2^2+2^1+2^0$$ Generalizing thus:- $$D(n)=2^kD(n-k)+2^{k-1}+2^{k-2}+...........+2^1+2^0$$ put $k=n-2$, we get: $$D(n)=2^{n-2}D(2)+2^{n-3}+2^{n-4}+........+2+1$$ $$\implies D(n)=2^{n-2}+.......+2+1$$ $$\implies D(n)=\frac{2^{n-1}-1}{2-1} \tag{Geometric progression}$$ $$D(n)=2^{n-1}-1$$ Verify it with John's answer.

Mayank Deora
  • 1,436