Strong induction on a summation of recursive functions (Catalan numbers) I've been stuck on how to proceed with this problem. All that's left is to prove this with strong induction:
$$\forall n \in \mathbb{N}, S(n) = \sum_{i=0}^{n-1} S(i)*S(n - 1 - i)$$
Some cases: S(0) = 1, S(1) = 1, S(2) = 2, S(3) = 5, S(4) = 14.
As I understand it, I should assume that $\forall k \in \mathbb{N}, k < n \implies S(k) = ...$. But then since $n-1 < n$, it must be true for $n-1$, so we'll have...
$$S(n-1) = \sum_{i=0}^{(n-1) - 1} S(i)*S((n-1) - 1 - i)$$
I can't figure out how to get from that to the conclusion though.
Any guidance would be appreciated.

You neglect to mention that $S(n)$ is the $n$th Catalan number. You're probably trying to prove some formula, say $S(n) = \varphi(n)$. For given $n$, you already know (this is the strong induction hypothesis) that $S(k) = \varphi(k)$ for $k < n$. Therefore
$$ S(n) = \sum_{i=0}^{n-1} S(i) S(n-1-i) = \sum_{i=0}^{n-1} \varphi(i) \varphi(n-1-i). $$
It remains to show that the right-hand side equals $\varphi(n)$, and then you can deduce that $S(n) = \varphi(n)$.
