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)
 
Hello, I'm joining this forum to ask two questions which have nagged me for some time. They both are presumed obvious, yet don't make sense to me. Nobody will explain their positions, which is...uh...aka science. I also have a thread for the other question. But this one involves probability, known as the Monty Hall Problem. Please see any number of YouTube videos on this for an explanation, I'll leave it to them to explain it. I question the predicate of all those who answer this...
I'm taking a look at intuitionistic propositional logic (IPL). Basically it exclude Double Negation Elimination (DNE) from the set of axiom schemas replacing it with Ex falso quodlibet: ⊥ → p for any proposition p (including both atomic and composite propositions). In IPL, for instance, the Law of Excluded Middle (LEM) p ∨ ¬p is no longer a theorem. My question: aside from the logic formal perspective, is IPL supposed to model/address some specific "kind of world" ? Thanks.
I was reading a Bachelor thesis on Peano Arithmetic (PA). PA has the following axioms (not including the induction schema): $$\begin{align} & (A1) ~~~~ \forall x \neg (x + 1 = 0) \nonumber \\ & (A2) ~~~~ \forall xy (x + 1 =y + 1 \to x = y) \nonumber \\ & (A3) ~~~~ \forall x (x + 0 = x) \nonumber \\ & (A4) ~~~~ \forall xy (x + (y +1) = (x + y ) + 1) \nonumber \\ & (A5) ~~~~ \forall x (x \cdot 0 = 0) \nonumber \\ & (A6) ~~~~ \forall xy (x \cdot (y + 1) = (x \cdot y) + x) \nonumber...
Back
Top