I'm trying to determine the order of growth of a recursive algorithm but I only got a recurrence. Please somebody explain me how to solve the following recurrence with $k = 2$:
$S(n,k)=kS(n-1,k)+S(n-1,k-1)$
$S(n,k)$ is an arbitrary function in terms of both $k$ and $n$
The answer is ${ 2 }^{ n-1 }-1$ but I don't know how to obtain it
Although you said that $S$ was an arbitrary function, it seems clear from the desired answer that $S$ is in fact the Stirling number of the second kind. $S(n,k)$ is the number of partitions of an $n$-element set into exactly $k$ non-empty parts. Thus, $S(n,1)=1$ for all $n\ge 1$, while $S(0,1)=0$. For $k=2$ your recurrence is
$$S(n,2)=2S(n-1,2)+S(n-1,1)=2S(n-1,2)+1$$
for $n\ge 2$. Clearly $S(1,2)=0$, since you can’t partition a singleton into two parts. Thus, if $a_n=S(n,2)$, you have
$$\begin{align*} a_1&=0\;,\text{ and}\\ a_n&=2a_{n-1}+1\quad\text{if}\quad n\ge 2\;. \end{align*}$$
Now prove by induction on $n$ that $a_n=2^{n-1}-1$ for $n\ge 1$.
By the way, it’s possible to derive this result directly. Let $S$ be a set of cardinality $n\ge 1$. To partition $S$ into $2$ sets, you can pick any non-empty subset $X$ that isn’t all of $S$ and use the partition $\{X,S\setminus X\}$. $S$ has $2^n$ subsets, but $X$ can’t be $\varnothing$ or $S$, so there are $2^n-2$ choices for $X$. However, every partition gets counted twice (why?), so there are actually only
$$\frac12\left(2^n-2\right)=2^{n-1}-1$$
such partitions.
