请输入您要查询的字词:

 

单词 ProofOfCatalansIdentity
释义

proof of Catalan’s Identity


For all positive integers i, let Fi denote the ith Fibonacci numberMathworldPlanetmath, with F1 = F2 = 1. We will show that for all positive integers n and r such that n>r the following holds:

Fn2-Fn+rFn-r=(-1)n-rFr2.

But in order to prove this we first need two lemmas:

Lemma 0.1.

For all positive integers a and b such that a>1, the identity

Fa+b=FaFb+1+Fa-1Fb

is true.

Proof.

We will prove this by inductionMathworldPlanetmath on b. When b=1, the identity states that

Fa+1=FaF2+Fa-1F1Fa+1=Fa1+Fa-11

which is true by the definition of the Fibonacci numbers. Now, assume for possible values of b less than some positive integer b0 such that b0>1, the propositionPlanetmathPlanetmathPlanetmath is true. Then

FaFb0+1+Fa-1Fb0
=Fa(Fb0+Fb0-1)+Fa-1(Fb0-1+Fb0-2)
=(FaFb0+Fa-1Fb0-1)+(FaFb0-1+Fa-1Fb0-2)
=Fa+(b0-1)+F(a-1)+(b0-1)(induction hypothesis)
=Fa+b0(definition of the Fibonacci numbers)

This concludes the proof. ∎

Lemma 0.2.

For all positive integers t such that t>1, the following holds:

Ft-12+FtFt-1-Ft2=(-1)t.
Proof.

We will (again) proceed by induction. First, when t=2, we have

F12+F2F1-F22=11+11-12=1

which is true. Now let us assume that the proposition is true forall positive integers which are greater than 1 and less than somepositive integer t0 (t0>2). Then

Ft0-12+Ft0Ft0-1-Ft02
=Ft0-12+(Ft0-1+Ft0-2)Ft0-1-(Ft0-1+Ft0-2)2
=Ft0-12+Ft0-12+Ft0-2Ft0-1-Ft0-12-Ft0-22-2Ft0-1Ft0-2
=Ft0-12-2Ft0-1Ft0-2-Ft0-22
=-(Ft0-22-2Ft0-2Ft0-1-Ft0-12)
=(-1)(-1)t0-1(by induction hypothesis)
=(-1)t0

and the proof is completePlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath.∎

Now to the main proposition. Let us make the substitutions x=n-rand a=r so that the theorem now states:

Theorem 0.3.

For all positive integers x and a, the following identity holds:

Fx+a2-Fx+2aFx=(-1)xFa2.
Proof.

We follow a series of calculations

Fx+a2-Fx+2aFx
=(FxFa+1+Fx-1Fa)2-(FxF2a+1+Fx-1F2a)Fx(by lemma 1)
=Fx2Fa+12+2FxFa+1Fx-1Fa+Fx-12Fa2-
Fx(Fx(Fa+12+Fa2)+Fx-1(FaFa+1+Fa-1Fa))(by lemma 1 again)
=FxFx-1Fa(Fa+1-Fa-1)+Fa2(Fx-12-Fx2)
=FxFx-1Fa(Fa)+Fa2(Fx-12-Fx2)(by the definition of Fibonacci numbers)
=Fa2(Fx-12+FxFx-1-Fx2)
=Fa2(-1)x(by lemma 2)

completing our proof of the theorem.∎

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 6:34:05