一类与迭代函数系统有关的组合恒等式

A Class of Combinatorial Identities Associatedwith Iterated Function SystemsHan-Ju Li and Yuan-Ling YeAbstractWe call a family of contractive maps{τi}N i=1on R an iterated function system(IFS).We prove that given an affine IFS on R and aprobability vector p then there exists a corresponding combinatorialidentity associated with binomial coefficients and moment sequencewith respect to the invariant measureµof IFS.In particular,whenµis the restriction of Lebesgue measure to a close interval,we obtainsome well-known or unknown combinatorial identities.Keywords:combinatorial identities,iterated function systems,binomial coefficient,invariant measure,Lebesgue measureMathematics Subject Classification:05A19,28C10,28A801IntroductionIt is well known that there are many methods to prove a known combinatorial identity,such as Snake Oil method and WZ method,see also[3],[8]and [9].This paper then does not relies on these combinatorial methods for proving combinatorial identities.Since these methods are no longer valid for the proof of Theorem1.1.While Theorem1.1contains some well-known combinatorial identities which can be proved by combinatorial methods.Our study is motivated by the famous Hausdorffmoment problem(see[2],[4]and[7])which may be stated as follows.Given a sequence of numbers{M n}∞n=0,under what conditions is it possible to determine a measureµon R such thatM n=Rx n dµ(x)for n=0,1,...Such a sequence is called a moment sequence with respect toµ.Then the combinatorial identity(1.0.2)shows a connection between moment sequence and binomial coefficients.1Let n jbe the number of ways of picking j unordered outcomes from n possibilities,i.e., n j=n !j !(n −j )!.We have the following theorem.Theorem 1.1Suppose that the affine IFS {τi }N i =1on R is given byτi (x )=λi x +b i ,where 0<λi <1.Let p =(p 1,p 1,···,p N )be a probability vector (i.e.p i >0and p i =1)and let µbe a finite measure with compact support X satisfying the following self-similar equationµ=N i =1p i µ◦τ−1i (1.0.1)in the sense thatµ(B )=N i =1p i µ(τ−1i (B ))for any Borel subset B of R .Denote the moment sequence M n = Rx n dµ(x ).Then we have the following combinatorial identityn j =0 n j Ni =1p i λj i b n −jiM j =M n ,(1.0.2)where M 0=µ(X ).Given an affine IFS {τi }N i =1on R and a probability vector p ,by a theoremof Hutchinson [6],there exists a unique probability measure µ(the invariant measure of IFS)with compact support X (X is just the attractor of IFS)satisfying the self-similar equation (1.0.1).Hence,from formula (1.0.2),we can get a combinatorial identity associated with binomial coefficient.In other words,an affine IFS on R and a probability vector can generate a combinatorial identity.We remark that the theory of IFS plays an important role in fractal image compression [1]and fractal geometry [5].In this paper we only take an interest in the case where µ=L |[a,b ],the restriction of2Lebesgue measure L to[a,b].This is because it is easy to compute the moment sequence with respect to L|[a,b],M j=R x j dµ(x)=bax j dx=b j+1−a j+1j+1.On the other hand,due to some results in§4,we can construct the measure µ=L|[a,b]easily.This paper is organized as follows.In§2we give a proof of Theorem1.1.In§3we deduce some well-known or unknown combinatorial identities from Theorem1.1and some results in§stly,in§4we study the Lebesgue measure induced by IFS.2Proof of TheoremProof.Wefirst want to show thatR f(x)dµ(x)=Ni=1p iRf(τi(x))dµ(x)(2.0.1)for every f(x)∈C(R).Let f(x)=X B(x)be the character function of Borel subset B of X.On the one hand,from(1.0.1),we haveR X B dµ=Ni=1p iRX B d(µ◦τ−1i) =Ni=1p iBd(µ◦τ−1i)=Ni=1p iµ(τ−1i(B)).On the other hand,Ni=1p iRX B◦τi dµ=Ni=1p iτ−1i(B)dµ=Ni=1p iµ(τ−1i(B)).It follows that(2.0.1)holds for every character function X B.Hence(2.0.1) holds for every simple function.Since for every continuous function there is a sequence of simple functions which uniformly converge to it,(2.0.1)also holds for every continuous function.3We use the notation00=1in the following argument,because it agrees with the Binomial expansion(x+0)n=nj=0njx j0n−j.Applying(2.0.1)to f(x)=x n and combining Binomial theorem,we haveM n=Ni=1p iR(λi x+b i)n dµ(x)=Ni=1p iRnj=0nj(λi x)j b n−jidµ(x)=Ni=1p inj=0njλjib n−jiM j=nj=0njNi=1p iλjib n−jiM j,which gives(1.0.2).It is clear thatM0=R1dµ(x)=µ(R)=µ(X),since X is the support ofµ.3Some ExamplesExample3.1(combinatorial identity induced by the middle-third Cantor measure)Ifµis a probability measure,we can compute M n exactly.For ex-ample,Letµbe the middle-third Cantor measure,i.e.,the unique probability measure satisfying the following self-similar equationµ=122i=1µ◦τ−1i,whereτ1(x)=x3,τ2(x)=x3+23.Then by Theorem1.1,we getM n=n−1j=0nj2n−j M j2(3n−1).4Note that M0=1,thereforeM1=12,M2=924,M3=65208,M4=11314160...We compare it with Lebesgue integral10x dx=12,1x2dx=824,1x3dx=52208,1x4dx=8324160...Example3.2Letα>0.Consider the IFSτ0(x)=xα+1,τ1(x)=αα+1x+1α.By Corollary4.2,the measureµ=L|[0,1]satisfies the following self-similarequationµ=1α+1µ◦τ−1+αα+1µ◦τ−11.Then by Theorem1.1,the formula(1.0.2)holds forλ0=p0=1α+1,λ1=p1=αα+1,b0=0,b1=1α+1.Note that00=1,we haveM n=nj=0nj1α+11α+1j0n−j+αα+1αα+1j1α+1n−jM j=nj=0njαα+1αα+1j1α+1n−jM j+M n(α+1)n+1=1(α+1)n+1nj=0njαj+1j+1+M n(α+1)n+1.A simple compute gives the following well-known combinatorial identityn j=0njαj+1j+1=(α+1)n+1−1n+1.Example3.3DenoteT m=nj=02n2j1m2j+1(2j+1),m∈N.ThenT m=(m+1)2n+1−(m−1)2n+1m2n+1(4n+2).5Proof.First,when m is odd,i.e.,m=2k−1,k∈N,we consider the IFSτi(x)=x2k+a i2k,i=0,1,...,2k−1.Where{a i}2k−1i=0is an arithmetic progression of length2k with initial terma0=1−2k and the common difference d=2,i.e.,a i=1−2k+2i,i= 0,1,...,2k−1.By Corollary4.3,the measureµ=L|[−1,1]satisfies the following self-similar equationµ=12k2k−1i=0µ◦τ−1i.Then by Theorem1.1,the formula(1.0.2)holds forλ0=···=λ2k−1=p0=···=p2k−1=1 2kandb0=−2k−12k,...,b i=1−2k+2i2k,...,b2k−1=2k−12k.Sinceµ=L|[−1,1]is the restriction of Lebesgue measure to[−1,1],we haveM j=R x j dµ(x)=1−1x j dx=1−(−1)j+1j+1.We also observe thata i+a2k−1−i=0,i=0,1,...,k−1. Hence we haveM n=nj=0nj2k−1i=012k12kja i2kn−jM j=nj=0njk−1i=012k12kja i2kn−j+12k12kja2k−1−i2kn−jM j=1(2k)n+1k−1i=0nj=0nja n−ji+(−a i)n−jM j=k−1i=0(2k−1−2i)n+1(2k)n+1nj=0nj[1+(−1)n−j][1−(−1)j+1](2k−1−2i)j+1(j+1)=ki=1(2i−1)n+1(2k)n+1nj=0nj[1+(−1)n−j][1−(−1)j+1](2i−1)j+1(j+1).6Moreover,we obtain ki=1(2i−1)n+1nj=0nj[1+(−1)n−j][1−(−1)j+1](2i−1)j+1(j+1)=(2k)n+1[1−(−1)n+1]n+1.Substituting2n for n,we obtain ki=1(2i−1)2n+12nj=02nj[1+(−1)2n−j][1−(−1)j+1](2i−1)j+1(j+1)=2·(2k)2n+12n+1.We observe that,if j=2m(m=0,1,...,n),then1+(−1)2n−j1−(−1)j+1=4,and if j=2m+1(m=0,1,...,n−1),then1+(−1)2n−j1−(−1)j+1=0.Which implies thatki=1(2i−1)2n+1T2i−1=(2k)2n+14n+2.(3.0.1)Letting k=1givesT1=nj=02n2j12j+1=4n2n+1.If k>1,thenk−1i=1(2i−1)2n+1T2i−1=(2k−2)2n+14n+2.(3.0.2)The difference of combination identity(3.0.1)and(3.0.2)givesT2k−1=(2k)n+1−(2k−2)n+1 (2k−1)2n+1(4n+2),which is accordant with the case k=1.Finally,when m is even,i.e.,m=2k,k∈N,we consider the IFSτi(x)=x2k+1+a i2k+1,i=0,1,...,2k.7Where a i=−k+i,By Corollary4.3,the measureµ=L|[−12,12]satisfiesthe following self-similar equationµ=12k+12ki=0µ◦τ−1i.Then by Theorem1.1,the formula(1.0.2)holds forλ0=···=λ2k=p0=···=p2k=12k+1,b0=−k2k+1,...,b i=−k+i2k+1,...,b2k−1=k2k+1.We observe that a i+a2k−i=0when i=0,1,...,k−1and thatM j=R x j dµ(x)=12−12x j dx=1−(−1)j+12j+1(j+1).Hence we haveM n=nj=0nj2ki=012k+112k+1ja i2k+1n−jM j=nj=0njk−1i=012k+112k+1ja i2k+1n−j+12k+112k+1ja2k−i2k+1n−jM j+M n(2k+1)n+1=1(2k+1)n+1k−1i=0nj=0nja n−ji+(−a i)n−jM j+M n(2k+1)n+1=k−1i=0(k−i)n+1(2k+1)n+1nj=0nj[1+(−1)n−j][1−(−1)j+1](2k−2i)j+1(j+1)+M n(2k+1)n+1=ki=1i n+1(2k+1)n+1nj=0nj[1+(−1)n−j][1−(−1)j+1](2i)j+1(j+1)+M n(2k+1)n+1.Moreover,we obtain ki=1i n+1nj=0nj[1+(−1)n−j][1−(−1)j+1](2i)j+1(j+1)=[(2k+1)n+1−1][1−(−1)n+1]2n+1(n+1).8Using the same argument as in the first part,we obtain the following com-binatorial identityk i =1i2n +1T 2i =(2k +1)2n +1−122n +2(2n +1).Which gives the following combinatorial identityT 2k=(2k +1)n +1−(2k −1)n +1(2k )2n +1(4n +2).This completes theproof.4Lebesgue Measure Induced by IFSMotivated by §3,in this section we will study Lebesgue measure inducedby IFS.Denote πλ(ω)= ∞i =1ωλi =ωλ+ωλ2+···=ωλ1−λ.We have the following proposition.Proposition 4.1Let p =(p 0,p 1,...,p m )be a probability vector and let the IFS {τi }m i =0on R consisting of m +1mappings be given byτ0(x )=p 0(x +a 0),τ1(x )=p 1(x +a 1),...,τm (x )=p m (x +a m ).We also assume that the IFS {τi }m i =0above satisfies the following end to end conditions:πp 0(a 0)<πp m (a m ),τi (πp m (a m ))=τi +1(πp 0(a 0)),i =0,1,...,m −1.Then µ=L |[πp 0(a 0),πp m (a m )]satisfies the following self-similar equationµ=m i =0p i µ◦τ−1i .(4.0.1)Proof.It is easy to verify that πp 0(a 0)and πp m (a m )are the fixed point ofmappings τ0(x )and τm (x )respectively,i.e.,τ0(πp 0(a 0))=πp 0(a 0),τm (πp m (a m ))=πp m (a m ).This,combined with the end to end conditions,implies that the close interval [πp 0(a 0),πp m (a m )]is the attractor of {τi },i.e.,[πp 0(a 0),πp m (a m )]=m i =0τi ([πp 0(a 0),πp m (a m )]).9Moreover,if j=i+1,thenτi([πp0(a0),πpm(a m)])∩τj([πp(a0),πpm(a m)])={τi(πpm(a m))}is a singleton,and if j−i≥2,thenτi([πp0(a0),πpm(a m)])∩τj([πp(a0),πpm(a m)])=∅.Denote X=[πp0(a0),πpm(a m)].Wefirst show that,for arbitrary B∈B(X),the self-similar equation(4.0.1)holds.Note that in this caseµ(B)=L(B∩X)=L(B),denote B i=B∩τi(X),we have∪m i=0B i=∪mi=0(B∩τi(X)),=B∩(∪mi=0τi(X))=B∩X=B,(4.0.2)since X is the attractor of{τi}.It is easy to see that B i⊂τi(X),so B i∩B j⊂τi(X)∩τj(X).It follows thatµ(B i∩B j)=0for i=j.This,combined with(4.0.2)and the including-excluding principle,we haveµ(B)=mi=0µ(B i)(4.0.3)On the other hand,for each i∈{0,1,...,m},we haveτ−1i(B)⊂X andτ−1 i (B)=τ−1i(B)∩τ−1i(τi(X)),=τ−1i(B∩τi(X))=τ−1i(B i).Thereforeµτ−1i(B)=Lτ−1i(B i)=L1p iB i−a i,=L1p iB i=1p iL(B i)=1p iµ(B i)(4.0.4)10where the third equation follows from the invariance of translation of Lebesgue measure and the four equation follows from the scaling property of Lebesgue bining(4.0.3)with(4.0.4),one can deduce the conclusion.Next we show that,for arbitrary B∈B(R),the self-similar equation (4.0.1)also holds.Let B1=B∩X,B2=B∩X c,then B=B1∪B2, B1∩B2=∅,B1∈B(X)andµ(B2)=L(B2∩X)=L((B∩X c)∩X)=0. Note thatτ−1 i (B2)∩X=τ−1i(B2)∩τ−1i(τi(X)),=τ−1i(B2∩τi(X))⊂τ−1i((B∩X c)∩X)=∅.Which implies thatµ(τ−1i (B2))=L(τ−1i(B2)∩X)=0.Thereforeµ(B)=µ(B1)+µ(B2),=mi=0p iµ(τ−1i(B1)+mi=0p iµ(τ−1i(B2)).=mi=0p iµ(τ−1i(B1)∪τ−1i(B2))=mi=0p iµ(τ−1i(B))where the third equation follows from the fact thatτ−1i (B1)∩τ−1i(B2)=τ−1 i (B1∩B2)=∅.Corollary4.2Letα>0.Consider the IFSτ0(x)=xα+1,τ1(x)=αα+1(x+β).Ifβ>0,thenµ=L|[0,αβ]satisfies the following self-similar equationµ=1α+1µ◦τ−1+αα+1µ◦τ−11.Ifβ<0,thenµ=L|[αβ,0]satisfies the following self-similar equationµ=1α+1µ◦τ−1+αα+1µ◦τ−11.11Proof.We only prove the caseβ>0.It is easy to verity thatπ1α+1(0)=0,παα+1(β)=αβα+1+α2β(α+1)2+···=αβ,andτ0(αβ)=αβα+1=τ1(0).So the end to end conditions hold.The desired result is obtained by Propo-sition4.1.. Corollary4.3For arbitrary arithmetic progression a0,a1,...,a m of length m+1with a0<a m.Consider the IFS{τi}consisting of m+1mappingsτi(x)=xm+1+a im+1,i=0,1,...,m.Thenµ=L|a0m,a mmsatisfying the following equationµ=1m+1mi=0µ◦τ−1i.Proof.By Proposition4.1,it suffices to verify the end to end conditions. Note thatπ1m+1(a0)=a0m+1+a0(m+1)2+···=a0mandπ1m+1(a m)=a mm+1+a m(m+1)2+···=a mm,which shows thatπ1m+1(a0)<π1m+1(a m),since a0<a m.Let d>0be the common difference of arithmetic progression a0,a1,...,a m,thena i=a0+id,i=0,1,...,m.For i∈{0,1,...,m−1},we haveτi−1π1m+1(a m)=τi−1amm=a m+ma i−1m(m+1)=a0+m(a i−1+d)m(m+1)=a0m(m+1)+a im+1 =τiam=τiπ1m+1(a0).Therefore the end to end conditionshold.12Example4.1Consider the IFSτ0(x)=x3,τ1(x)=x3+13,τ2(x)=x3+43.Clearly,{0,1,4}is not an arithmetic progression.It is easy to verify that [0,2]is the attractor of{τ0,τ1,τ2}.But the measureµ=L|[0,2]does not satisfying the following equationµ=132i=0µ◦τ−1i.In fact,Let[13,23]∈B([0,2]),thenµ13,23=13and132i=0µτ−1i13,23=23.Which is a contraction.References[1]M.F.Barnsley and L.P.Hurd,Fractal image compression,Wellesley,Massachusetts:AK Peters,1993.[2]B.Simon,The classical moment problem as a self-adjointfinite differenceoperator,Adv.Math.137(1998),82-203.[3]D.Klarner,Some results concerning polyominoes,Fibonacci Quart.3(1965),9-20.[4]F.Hausdorff,Summationsmethoden und Momentfolgen.I,Math.Z.9(1921),74-109.[5]K.J.Falconer,Fractal geometry:Mathematical foundation and appli-cations,New York:Wiley,1990.[6]J.E.Hutchinson,Fractals and self-similarity,Indiana Univ.Math.J.30(1981),713-747.[7]N.I.Akhiezer,The classical moment problem and some related ques-tions in analysis,Oliver and Boyd,Edinburgh.(Russian edition,Moscow 1961).13 [8]H.S.Wilf and D.Zeilberger,Rational functions certify combinatorialidentities,J.Amer.Math.Soc.3(1990),147-158.[9]H.S.Wilf and D.Zeilberger,An algorithmic proof theory for hyper-geometric(ordinary and”q”)multisum/integral identities,Inventions Mathematica.108(1992),575-633.School of Mathematical SciencesSouth China Normal UniversityGuangzhou510631,P.R.China.hanjuli@School of Mathematical SciencesSouth China Normal UniversityGuangzhou510631,P.R.China.ylye@14。