MHB Proving the Solution of a Recurrence Relation Using Induction

  • Thread starter Thread starter mathmari
  • Start date Start date
AI Thread Summary
The discussion focuses on proving the solution of the recurrence relation defined by X(1)=1 and X(n)=∑(i=1 to n-1)X(i)X(n-i) for n>1, with the proposed solution X(n+1)=1/(n+1) * C(2n, n). The user has successfully verified the base case and made an induction assumption for k values up to n. They are now attempting to show the case for n+1, involving complex summations and factorials. The user is considering whether to apply combinatorial formulas, specifically C(2n, n)=∑(k=0 to n)C(n, m)^2, to help in their proof. The discussion highlights the challenges in continuing the proof and the potential need for combinatorial insights.
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

I have to show that the solution of the recurrence $$X(1)=1, X(n)=\sum_{i=1}^{n-1}X(i)X(n-i), \text{ for } n>1$$
is $$X(n+1)=\frac{1}{n+1} \binom{2n}{n}$$

I used induction to show that.

I have done the following:

For $n=0$ : $X(1)=1 \checkmark $

We assume that it stands for each $1 \leq k \leq n$:
$$X(k)=\frac{1}{k}\binom{2(k-1)}{k-1} \ \ \ \ \ (*)$$

We want to show that it stands for $n+1$:

$$X(n+1)=\sum_{i=1}^{n} X(i)X(n+1-i)=\sum_{i=1}^{n} \frac{1}{i}\binom{2(i-1)}{i-1}\frac{1}{n+1-i}\binom{2(n-i)}{n-i}=\sum_{i=1}^{n}\frac{1}{i}\frac{(2(i-1))!}{(i-1)!(2(i-1)-(i-1))!}\frac{1}{n+1-i}\binom{(2(n-i))!}{(n-1)!(2(n-i)-(n-i))!}=\sum_{i=1}^{n}\frac{(2(i-1))!}{i!(i-1)!}\frac{(2(n-i))!}{(n-i+1)!(n-i)!}$$

How could I continue?? (Wondering)
 
Physics news on Phys.org
Do we have to use maybe a formula from combinatorics, for example $$\binom{2n}{n}=\sum_{k=0}^{n}\binom{n}{m}^2$$ ?? (Wondering)
 
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...
Back
Top