Recurrence Relations - discrete math 
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?
 A: 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.
A: 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.
