Coeciente binomial 2RodrigoCarlosSilvadeLima UniversidadeFederalFluminense-UFF-RJrodrigo.u.math@gmail.com1Sumario1 Coecientebinomial 31.1 Algumasmanipulacoesenvolvendocoecientebinomial . . . . . . . . . . . 31.1.1 Func aogeradora . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.1.2 Tornandonegativoonumerador . . . . . . . . . . . . . . . . . . . . 51.2 Propriedadesdeabsorc ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.2.1 Absorcaom ultipla . . . . . . . . . . . . . . . . . . . . . . . . . . . 181.3 Seriedepotenciasfatoriais . . . . . . . . . . . . . . . . . . . . . . . . . . . 191.4 Analogiasentreidentidadesdocalculoedocalculonito . . . . . . . . . . 251.5 Exercciosdotexto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281.5.1 Propriedadesbasicas . . . . . . . . . . . . . . . . . . . . . . . . . . 281.5.2 Somatorios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291.5.3 N umerosdeCatalan . . . . . . . . . . . . . . . . . . . . . . . . . . 331.6 Coecientebinomialen umerosdeFibonacci . . . . . . . . . . . . . . . . . 351.7 CrescimentoeDescrescimentodocoecientebinomial . . . . . . . . . . . . 381.8 Derivac aoeintegrac aodocoecientebinomial . . . . . . . . . . . . . . . . 411.9 Somatoriodesomatorioscomocoecientebinomial . . . . . . . . . . . . . 431.10 Coecientebinomialen umerosHarmonicos . . . . . . . . . . . . . . . . . 441.11 Somatorioseseriescomcoecientebinomial . . . . . . . . . . . . . . . . . 441.12 Calculodealgunsvaloresespeciaisdocoecientebinomial . . . . . . . . . 451.13 Coecientebinomialecombinat oria. . . . . . . . . . . . . . . . . . . . . . 452Captulo1Coecientebinomial1.1 Algumas manipulacoes envolvendo coeciente bi-nomialExemplo1. Sabemosque2n=nk=0_nk_pelaexpansaopelobinomiodeNewtonde(1 + 1)n, sabemostambemquef(n) =2n,satisfazarecorrenciaf(n + 1) = 2f(n)comf(0) = 1,vamosmostrarentaoaidentidademanipulandoapenasosomatoriodoscoecientesbinomiais.Temosf(0) =0k=0_0k_ =_00_ = 1.entaosatisfazacondic aoinicial, agoravamosmostrarquesatisfazarecorrencia, temosquemostrarquef(n + 1) 2f(n) = 0temosf(n + 1) 2f(n) =n+1k=0_n + 1k_2nk=0_nk_ =nk=1_n + 1k_ + 1 + 1 2nk=0_nk_ =3CAPITULO1. COEFICIENTEBINOMIAL 4usandoagoraarelacaodeStifelnoprimeirosomatorio=nk=1_nk_ +nk=1_nk 1_ + 1 + 1 2nk=0_nk_ =subtraindo1doslimitesdosegundosomatorioeabsorvendo1paraolimiteinferiordoprimeirosomatorio=nk=0_nk_+n1k=0_nk_ + 1 2nk=0_nk_absorvendo1paraolimitesuperiordosegundosomatorionk=0_nk_ +nk=0_nk_2nk=0_nk_ = 0.1.1.1 FuncaogeradoraSabemosqueocoecientebinomialeocoecientedasxpotenciasdexnaexpansao(1 + x)n,vamospartirdarelac aodeStifelf(n + 1, k + 1) = f(n, k + 1) + f(n, k)edascondic oesdecontornof(n, n) = 1,f(n, 0) = 1ef(n, k) = 0sek > nededuzirqueafunc aoquesatisfazessasrelacoes eocoecientebinomial. Partimosdarecorrenciaf(n + 1, k + 1) = f(n, k + 1) + f(n, k)multiplicandoporxketomandosomatorioem[0, )edeixandoosomatoriocomlimitesuperiornitopelacondic aodecontornonk=0xkf(n + 1, k + 1) =n1k=0xkf(n, k + 1) +nk=0xkf(n, k)fazendomudan canoslimites1xn+1k=1xkf(n + 1, k) =1xnk=1xkf(n, k) +nk=0xkf(n, k) =completandoossomatorios=1x_n+1k=0xkf(n + 1, k) 1_ =1x_nk=0xkf(n, k) 1_+nk=0xkf(n, k)CAPITULO1. COEFICIENTEBINOMIAL 5chamandog(x, n) =nk=0xkf(n, k)temos1x_g(x, n + 1) 1_ =1x_g(x, n) 1_ + g(x, n)multiplicandoaexpressaoporxg(x, n + 1) 1 = g(x, n) 1 + x.g(x, n)logotemosg(x, n + 1) = (1 + x)g(x, n)Qg(x, k) = (1 + x)ondeoquociente etomadoemrelac aoak,tomandooprodutorioem[0, n 1]n1k=0Qg(x, k) =g(x, n)g(x, 0)=n1k=0(1 + x) = (1 + x)ncomog(x, 0) =0k=0xkf(0, k) = f(0, 0) = 1temosg(x, n) = (1 + x)n=nk=0xkf(n, k).1.1.2 Tornandonegativoonumerador Propriedade1._rk_ = (1)k_k r 1k_.Demonstracao.(1)k_k r 1k_ = (1)k(k r 1)(k,1)k!=r(k,1)k!=_rk_ondeusamospropriedadedepotenciafatorial. Multiplicandoaidentidadepor(1)kemambosladossegue(1)k_rk_ =_k r 1k_(1)k_r 1k_ =_k rk_trocandorpor rnaprimeira(1)k_rk_ =_k + r 1k_CAPITULO1. COEFICIENTEBINOMIAL 6 Corolario1. Tomandoaidentidade_rk_ = (1)k_k r 1k_efazendor = 1_1k_ = (1)k_k + 1 1k_ = (1)k_kk_ = (1)kentaosekepar_1k_ = 1seke mpar_1k_ = 1,comknatural.Exemplo2. lim_1k_k= 0pois_1k_ = (1)ke((1)k) eumasequencialimitadae(1k) eumasequenciaquetendeazero. Propriedade2._n + mn_ =_n + mm_paramennaturais.Demonstracao._n + mn_ =(n + m)!n!m!_n + mm_ =(n + m)!m!n!logosaoiguais. Propriedade3.(1)m_n 1m_ = (1)n_m1n_param, nnaturais.Demonstracao. Usamosaidentidade(1)k_rk_ =_k r 1k_segue(1)m_n 1m_ =_m + nm_(1)n_m1n_ =_n + mn_CAPITULO1. COEFICIENTEBINOMIAL 7maspelapropriedadeanterior_m + nm_ =_n + mn_logo(1)m_n 1m_ = (1)n_m1n_. Corolario2. Podemosagoracalcularasomamk=0(1)k_nk_ =mk=0_k n 1k_ =_mnm_ = (1)m_n 1m_mk=0(1)k_nk_ =_mnm_.mk=0(1)k_nk_ = (1)m_n 1m_.Exemplo3. Mostrarquepk=0_m + kk__n kp k_ =_m + n + 1p_.Valemasidentidade_n kp k_ = (1)p+k_p n 1p k__m + kk_ = (1)k_m1k_substituindonasomatemospk=0_m + kk__n kp k_ =pk=0(1)p_m1k__p n 1p k_ = (1)p_p (m + n + 1) 1p_ =ondeessa ultimapartesaidaconvoluc aodeVandermonde,porem(1)p_p (m + n + 1) 1p_ =_m + n + 1p_.CAPITULO1. COEFICIENTEBINOMIAL 8Exemplo4. Resolveraequacaonk=0_(1)kkj=1(x j + 1)k!_ = 0.Primeiromanipulamosoprodutoriokj=1(x j + 1) =k1j=0(x j) = x(k,1)Daasoma enk=0_(1)kkj=1(x j + 1)k!_ =nk=0(1)k_xk_ = (1)n_x 1n_sejaent aonxo,sen = 0naotemossoluc ao,sen > 0podemosescrever_x 1n_ =n1s=0(x 1 s)n!onde no numerador temos um polinomio de grau n em x, tendo no maximo n razes reaisepelaformadoprodutoriovemosqueasrazessaox=1 + scomsvariandode0aten 1, istoetemosrazesx=1atex=neapenasestas, porcausadalimitacaodetermosapenasnrazesparaopolinomiodegraun. Propriedade4. Valet=0_t + ss_at=1(1 a)(s+1).Demonstracao. Tomandoaseriebinomial (1 + x)r=t=0_rt_(x)t, x= aer = (s + 1)segue1(1 a)s+1=t=0_s 1t_(1)t(a)tusamosapropriedade_s 1t_(1)t=_t + st_ =_t + ss_,logot=0_t + ss_at=1(1 a)(s+1).CAPITULO1. COEFICIENTEBINOMIAL 91.2 Propriedadesdeabsorcao Propriedade5._nk_k + p=1(n + 1)(p,1)_n + pk + p_(k + 1)(p1,1)_nk_k + p=1ps=1(n + s)_n + pk + p_p1s=1(k + s).Demonstracao._nk_k + p=n(k,1)(k + p)(k)!multiplicandopeloprodutoriok+p1s=k+1s =p2s=0(k + 1 + s) = (k + 1)(p1,1)onumeradoreodenominador,teremosnodenominador(k) = [ks=1s][k+p1s=k+1s](k + p) =k+ps=1s = (k + p)!candocom_nk_k + p=n(k,1)(k + 1)(p1,1)(k + p)!multiplicandoonumeradoreodenominadoragorapeloprodutoriops=1(n + s) =p1s=0(n + 1 + s) = (n + 1)(p,1)temosnonumeradorn(k,1)ps=1(n+s) =k1s=0(ns)ps=1(n+s) =k1s=0(ns)0s=1p(n+p+s) =p+k1s=p(n+ps)p1s=0(n+ps) ==p+k1s=0(n + p s) = (n + p)(k+p,1)ondetemosnalmente_nk_k + p=(n + p)(k+p,1)(k + 1)(p1,1)(k + p)!(n + 1)(p,1)CAPITULO1. COEFICIENTEBINOMIAL 10nk=0_nk_k + p=nk=0(n + p)(k+p,1)(k + 1)(p1,1)(k + p)!(n + 1)(p,1)mascomo(n + p)(k+p,1)(k + p)!=_n + pk + p_segue_nk_k + p=1(n + 1)(p,1)_n + pk + p_(k + 1)(p1,1). Propriedade6._nk_ps=1(k + s)=_n+pk+p_ps=1(n + s)_nk_(k + 1)(p,1)=_n+pk+p_(n + 1)(p,1)(k)(p,1)_nk_ = (n)(p,1)_n + pk + p_parapnatural._nk_ps=1(k + s)=n(k,1)k!ps=1(k + s)nodenominadortemosk!ps=1(k + s) =ks=1(s)p+ks=1+k(s) =p+ks=1(s) = (k + p)!eonumeradormultiplicamosporps=1(n + s)=(n + 1)(p,1)manipulacaoquejazemosemoutrocoecientebinomial,oresultadononumeradorca(n + p)(k+p,1),logotemos_nk_ps=1(k + s)=1(n + 1)(p,1)(n + p)(k+p,1)(k + p)!=1(n + 1)(p,1)_n + pk + p__nk_ps=1(k + s)=_n+pk+p_ps=1(n + s).CAPITULO1. COEFICIENTEBINOMIAL 11 Propriedade7.(k)(p,1)_nk_ = (n)(p,1)_n pk p_parapnaturalek pnatural.EssapropriedadedizqueDemonstracao.k(p,1)_nk_ =p1s=0(k s)n(k,1)k!=p1s=0(k s)n(k,1)ks=1s=0s=1p(k + s)n(k,1)ks=1s==ks=1+kp(s)n(k,1)ks=1s=agoraabrimosoprodutoriododenominadorks=1s =kps=1sks=1+kps =kps=1s.(k p)!anulandoostermoscomunsdonumeradoredenominador=n(k,1)(k p)!=agoranonumeradorusamosapropriedadedeaberturan(k,1)= n(p,1)(n p)(kp,1)logotemos= n(p,1)(n p)(kp,1)(k p)!= n(p,1)_n pk p_. Corolario3. Daidentidade(k)(p,1)_nk_ = (n)(p,1)_n pk p_dividindoporp!segue_kp__nk_ =_np__n pk p_.CAPITULO1. COEFICIENTEBINOMIAL 12 Observacao1(Propriedadedeabsorc ao). Apropriedadedeabsorc aovaleparatodopinteiroemk(p,1)_nk_ = n(p,1)_n pk p_.Essapropriedadenosdizqueocoecientebinomial absorveotermok(p,1)edevolveotermon(p,1)Vamosmostrarqueapropriedadevaleparatodoprealatravesdafuncaogammak(p,1)_nk_ =(k + 1)(k p + 1)(n + 1)(k + 1)(n k + 1)==1(k p + 1)(n + 1)(n k + 1)=(n + 1)(n p + 1)(n p + 1)(k p + 1)(n k + 1)= n(p,1)_n pk p_ Corolario4. Dapropriedadedeabsorc aok(p,1)_nk_ = n(p,1)_n pk p_.dividindoambostermosporp!temosk(p,1)p!_nk_ =n(p,1)p!_n pk p_ =_kp__nk_ =_np__n pk p_queimplica_kp__np_=_npkp__nk_ . Corolario5. De_kp__nk_ =_np__n pk p_Somandodep = 0atekseguekp=0_kp__nk_ =kp=0_np__n pk p_ =_nk_kp=0_kp_ =_nk_2k. Corolario6. Daidentidade_kp__np_=_npkp__nk_ .CAPITULO1. COEFICIENTEBINOMIAL 13podemoscalcularumoutrotipodesomatoriobinomialkp=0_kp__np_=kp=0_npkp__nk_ =1_nk_kp=0_n pk p_ =1_nk_0p=k_n + pk + p_ =1_nk_kp=0_n k + pp_ ==1_nk__k + 1 + n kk_ ==1_nk__n + 1k_ =(n + 1)!k!(n + 1 k)!k!(n k)!n!=(n + 1)(n + 1 k)kp=0_kp__np_=(n + 1)(n + 1 k).Exemplo5. Podemosgeneralizarapropriedadeanteriorusandoquepk=0_m + kk__t r kp k_ =_m + t r + 1p_e_m+kk__trkpk__tpm__tp_ =_pk__tm+k_temospk=0_pk__tm+k_=1_tpm__tp_pk=0_m + kk__t r kp k_ =_m + t r + 1p_1_tpm__tp_Exemplo6. Demonstramosquenk=0_rk__sn k_ =_r + sn_.Vamoscalcularnk=0k(p,1)_rk__sn k_parapnatural.Usandoapropriedadedeabsorc aotem-sek(p,1)_rk_ = r(p,1)_r pk p_substituindonasomank=0k(p,1)_rk__sn k_ =nk=pk(p,1)_rk__sn k_ = r(p,1)nk=p_r pk p__sn k_ =CAPITULO1. COEFICIENTEBINOMIAL 14= r(p,1)npk=0_r pk__sn p k_ = r(p,1)_r p + sn p_logonk=0k(p,1)_rk__sn k_ = r(p,1)_r p + sn p_. Corolario7. Dividindoporp!a ultimaidentidadeseguenk=0_kp__rk__sn k_ =_rp__r p + sn p_. Corolario8. Sep = 1,tem-senk=0k_rk__sn k_ = r_r 1 + sn 1_Fazendos = nseguenk=0k_rk__nn k_ =nk=0k_rk__nk_ = r_r 1 + nn 1_enalmentetomandor = nnk=0k_nk_2= n_2n 1n 1_ Corolario9. Tomandor = n = semnk=0_kp__rk__sn k_ =_rp__r p + sn p_.seguenk=0_kp__nk_2=_np__2n pn p_ Corolario10. Podemosexpressarnk=0kp_rk__sn k_transformamoskpemsomadepotenciasfatoriaiseaplicamosoresultadokp=pu=0_pu_k(u,1)CAPITULO1. COEFICIENTEBINOMIAL 15logonk=0kp_rk__sn k_ =pu=0_pu_nk=0k(u,1)_rk__sn k_ =pu=0_pu_r(u,1)_r u + sn u_.nk=0kp_rk__sn k_ =pu=0_pu_r(u,1)_r u + sn u_nk=0kp_rk__sn k_ =pu=0_pu__ru__r u + sn u_u! Propriedade8.nk=0k2_nk_2= n2_2n 2n 1_Demonstracao. Primeirovamos provar aseguinte propriedade de potenciasfatoriais(2n 1)(n1,1)+ (n 1)2(2n 2)(n2,1)= n(2n 2)(n1,1)oladodireitoen(2n 2)(n1,1)=n(2n 2)(n2,1)(2n 2 n + 2)=n2(2n 2)(n2,1)entaotemosquemostrarqueoladoesquerdo eissotambem(2n1)(n1,1)+(n1)2(2n2)(n2,1)= (2n1)(2n2)(n2,1)+(n1)2(2n2)(n2,1)== (2n 1 + n22n + 1)(2n 2)(n2,1)= n2(2n 2)(n2,1)logo esta provada a identidade. Dividindo a identidade por (n1)! em ambos lados segue(2n 1)(n1,1)(n 1)!+ (n 1)(2n 2)(n2,1)(n 2)!= n(2n 2)(n1,1)(n 1)!==_2n 1n 1_+ (n 1)_2n 2n 2_ = n_2n 1n 1_multiplicandoessaidentidadepornseguen_2n 1n 1_ + n(n 1)_2n 2n 2_ = n2_2n 1n 1_.Usamosagoraapropriedadenk=0kp_rk__sn k_ =pu=0_pu_r(u,1)_r u + sn u_CAPITULO1. COEFICIENTEBINOMIAL 16parap = 2r = s = nnk=0k2_nk__nn k_ =nk=0k2_nk_2=2u=0_2u_n(u,1)_2n un u_ ==_21_n(1,1)_2n 1n 1_+_22_n(2,1)_2n 2n 2_ = n_2n 1n 1_+n(n1)_2n 2n 2_ = n2_2n 1n 1_.Demonstracao.nk=1k2_nk_2=usandoquek_nk_=n_n 1k 1_temosk2_nk_2=n2_n 1k 1_2subtituindonasomasegue= n2n1i=0_n 1k_2= n2_2n 2n 1_.Exemplo7. Calcularnk=0_kp_2_nk_2.Temos_kp__nk_ =_np__n pk p_ logo_kp_2_nk_2=_np_2_n pk p_2,aplicando na somaseguenk=p_kp_2_nk_2=_np_2 nk=p_n pk p_2=_np_2npk=0_n pk_2=_np_2_2n 2pn p_.Logonk=0_kp_2_nk_2=_np_2_2n 2pn p_.Exemplo8. Vamoscalcularnk=0k(p,1)_rk__sn k_.Porpropriedadedeabsorcaotemosnk=0k(p,1)_rk__sn k_ = r(p,1)nk=0_r + pk + p__sn k_ = r(p,1)n+pk=p_r + pk__sn + p k_ =CAPITULO1. COEFICIENTEBINOMIAL 17= r(p,1)_n+pk=0_r + pk__sn + p k_p1k=0_r + pk__sn + p k__ == r(p,1)__r + p + sn + p_p1k=0_r + pk__sn + p k__.nk=0k(p,1)_rk__sn k_ = r(p,1)__r + p + sn + p_p1k=0_r + pk__sn + p k__. Corolario11. Tomandop = 1temosnk=01k + 1_rk__sn k_ =1r + 1__r + 1 + sn + 1__sn + 1__tomandor = s = ntemosnk=01k + 1_nk__nk_ =1n + 1__n + 1 + nn + 1__nn + 1__ =1n + 1_2n + 1n + 1_nk=01k + 1_nk_2=1n + 1_2n + 1n + 1_.Exemplo9. Calcularnk=01k + 1_n 1k__nk_.Tomandonk=01k + 1_rk__sn k_ =1r + 1__r + 1 + sn + 1__sn + 1__fazendor = n 1es = ntem-senk=01k + 1_n 1k__nk_ =1n_2nn + 1_.Exemplo10. Calcularnk=1_nk__nk 1_.nk=1_nk__nk 1_ =n1k=0_nk + 1__nk_ =nk=0_nk + 1__nk_como_nk + 1_ =nk + 1_n 1k_asomacacomonnk=01k + 1_n 1k__nk_ =_2nn + 1_CAPITULO1. COEFICIENTEBINOMIAL 18nk=1_nk__nk 1_ =_2nn + 1_.Exemplo11. Calcularasomank=1__nk__nk 1__2.Usandoque__nk__nk 1__2=_nk_22_nk__nk 1_ +_nk 1_2aplicandoasoma,tem-senk=1_nk_22nk=1_nk__nk 1_+nk=1_nk 1_2==_2nn_1 2_2nn + 1_ +_2nn_1 = 2_2nn_2 2_2nn + 1_1.2.1 Absorcaom ultipla Propriedade9. Valeapropriedade[vs=1_k st=2pt1ps_]_nk_ = [vs=1_n st=2pt1ps_]_n vt=1ptk vt=1pt_.Porinducao,parav= 1[_kp1_]_nk_ =_np1__n p1k p1_.Supondovalidaparav[vs=1_k st=2pt1ps_]_nk_ = [vs=1_n st=2pt1ps_]_n vt=1ptk vt=1pt_.vamosprovarparav + 1[v+1s=1_k st=2pt1ps_]_nk_ = [v+1s=1_n st=2pt1ps_]_n v+1t=1ptk v+1t=1pt_.CAPITULO1. COEFICIENTEBINOMIAL 19Multiplicamosahipotesedainducaopor_k v+1t=2pt1pv+1_ =_k vt=1ptpv+1__k v+1t=2pt1pv+1_[vs=1_k st=2pt1ps_]_nk_ = [vs=1_n st=2pt1ps_]_n vt=1ptk vt=1pt__k vt=1ptpv+1_ == [v+1s=1_k st=2pt1ps_]_nk_ = [vs=1_n st=2pt1ps_]_n v+1t=2pt1pv+1__n vt=1pt pv+1k vt=1pt pv+1_ == [v+1s=1_k st=2pt1ps_]_nk_ = [v+1s=1_n st=2pt1ps_]_n v+1t=1ptk v+1t=1pt_.Demonstracao. Denicao 1(Coecientemultinomial). Denimosocoecientemultinomialcomo_nk=1ak(ak)n1_ :=n1s=1_bs+1bs_ =bn!nk=1(ak)!.ondebs=sk=1ak1.3 SeriedepotenciasfatoriaisSejaumafunc aodadaporf(x) =k=0akx(k,1)k!=k=0ak_xk_Pois_xk_ =x(k,1)k!. Teorema 1.f(n) =k=0ak_nk_ =nk=0ak_nk_Senumn umeronatural.CAPITULO1. COEFICIENTEBINOMIAL 20Demonstracao. Pelapropriedadedepotenciafatorialtemos(p)(k,1)= 0Sek > p. Abrindoosomatoriotemosf(n) =k=0ak_nk_ =nk=0ak_nk_+k=n+1ak_nk_k=n+1ak_nk_ = 0 =k=n+1akn(k,1)k!Poisk > n. Entaocamoscomf(n) =k=0ak_nk_ Teorema 2.pf(x) =k=0a(k+p)x(k,1)k!=k=0a(k+p)_xk_Demonstracao. Parap = 0aproposic ao everdadeirapois0f(x) = f(x) =k=0a(k)x(k,1)k!=k=0a(k+0)x(k,1)k!=k=0a(k)_xk_Sejaaproposicaovalidaparap,pf(x) =k=0a(k+p)x(k,1)k!Vamosprovarparap + 1p+1f(x) =k=0a(k+p+1)x(k,1)k!temosquep+1f(x) =[pf(x)] =p[f(x)], aplicandoentaoooperadorDeltanosomatorio,camoscomp+1f(x) =k=0a(k+p)x(k,1)k!=k=0a(k+p)kx(k1,1)k!abrindooprimeirotermotemosa(0+p)0x(k1,1)k!+k=1a(k+p)kx(k1,1)k!=k=1a(k+p)kx(k1,1)k!=k=1a(k+p)x(k1,1)(k 1)!somando 1aolimitesuperioreinferiorcamoscomk=0a(k+p+1)x(k,1)k!= p+1f(x).CAPITULO1. COEFICIENTEBINOMIAL 21Exemplo12. Sejaf(x) =k=0ak_xk_eumaequac aodediferencapf(x) = f(x).Temosent aok=0ak+p_xk_ =k=0ak_xk_k=0ak+p_xk_k=0ak_xk_ = 0k=0[ak+p ak]_xk_ = 0Umacondic ao equeak+p= ak.Exemplo13. Sejaafunc aodenidacomof(n) =nk=0a(k)_nk_ =coma(k + 3) = a(k)ea(0) = 1,a(1) = a(2) = 0=_n0_ +_n3_ +_n6_+ ...achesuaformafechada. Comotemosa(k + 3) a(k) = 0multipliquetudopor_nk_etomeasomadekvariandodezeroateinnitok=0_a(k + 3) a(k)__nk_ = 0k=0a(k + 3)_nk_ =k=0a(k)_nk_CAPITULO1. COEFICIENTEBINOMIAL 22setemosf(n) =k=0a(k)_nk_entao3f(n) =k=0a(k + 3)_nk_logotemos3f(n) = f(n)quepodeserresolvidapelosmetodosdeequacoesdediferencas. Corolario12. Setemosumafuncaodenidacomof(n) =k=0_nk_g(k)ondeg(k)satisfazumarecorrenciadaformaps=0asg(k + s) =ps=0asEsg(k) = 0podemosaplicarooperadorps=0assemf(n)ps=0assf(n) =ps=0ask=0_nk_g(k + s) =k=0_nk_ps=0asg(k + s) = 0logof(n)satisfazarecorrenciaps=0assf(n) = 0istoepodemosmudararecorrenciadoscoecientesdiretamenteparaarecorrenciadafuncaotrocandoooperadorEspors. Entaotemosoresultado: Sef(n) =k=0_nk_g(k)evaleps=0asEsg(k) = 0CAPITULO1. COEFICIENTEBINOMIAL 23entaovaleps=0assf(n) = 0. Teorema 3. Valeapropriedade(E a)pf(n) =k=0[(E a + 1)pg(k)]_nk_ondef(n) =k=0g(k)_nk_g(k) e uma sequencia qualquer e p e um n umero natural. Vamos demonstrar por inducaosobrep,parap = 0temos(E a)0f(n) = f(n) =k=0[(E a + 1)0g(k)]_nk_.Considerandovalidaahipotese(E a)pf(n) =k=0[(E a + 1)pg(k)]_nk_vamosdemonstrar(E a)p+1f(n) =k=0[(E a + 1)p+1g(k)]_nk_temosaplicandoE a = E 1 a + 1 = + 1 anahipotese(E a)p+1f(n) = ( + 1 a)k=0[(E a + 1)pg(k)]_nk_ ==k=0[(E a + 1)pg(k + 1)]_nk_ + (1 a)k=0[(E a + 1)pg(k)]_nk_ ==k=0[(E a + 1)p(E + 1 a)g(k)]_nk_ ==k=0[(E a + 1)p+1g(k)]_nk_. Corolario13. Sea = 2temos(E 2)pf(n) =k=0[(E 2 + 1)pg(k)]_nk_ =k=0[(E 1)pg(k)]_nk_ =k=0pg(k)_nk_.CAPITULO1. COEFICIENTEBINOMIAL 24 Corolario14. Seg(k) =pl=0alklumpolinomiodegraup,segue(E 2)p+1f(n) =k=0p+1g(k)_nk_ = 0comoarecorrencia edaforma(E 2)p+1f(n) = 0entaof(n) edaformaf(n) = 2nps=0csns. Corolario15. Sejaagoraf(n) =k=0g(k)qk_nk_onde g(k) e de grau p. Sabemos que (Eq)p+1[g(k).qk] = [p+1g(k)][Ep+1qk] = 0 e temosk=0(E q)p+1[g(k).qk]_nk_ = (E (q + 1))p+1f(n) = 0logof(n) edaformaf(n) = (q + 1)nps=0csns.CondicoesiniciaisSetemosf(x) =k=0g(k)_xk_temosf(0) =k=0g(k)_0k_ = g(0)emgeralsf(0) =k=0g(k + s)_0k_ = g(s)f(0) = g(0)sf(0) = g(s).CAPITULO1. COEFICIENTEBINOMIAL 251.4 Analogias entre identidades do calculo e do calculonitoSabemosquek=0_nk_ = 2ntemos2n= 2neaseriek=0xkk!=k=0_xk_0= exeDex= ex.Exemplo14.k=0(1)kx2k+1(2k + 1)!= senx =k=0(1)k_x2k + 1_0Vamosacharexpressaoparak=0(1)k_x2k + 1_ =k=0g(k)_xk_ = f(x)temosg(k + 2)= g(k)comg(0)=0=f(0)eg(1)=1=f(0)assimf(x)satisfazarecorrencia2f(x) = f(x)entaoasolucao edotipof(x) = c1sen(x, 1) + c2cos(x, 1)comof(0)=0temosf(0)=c1sen(0, 1) + c2cos(0, 1)=c2=0ef(x)=c1cos(x, 1),f(0) = c1cos(0, 1) = c1= 1logoafunc ao ef(x) = sen(x, 1) =2xsenx4.Temosent aok=0(1)kx2k+1(2k + 1)!= senxk=0(1)kx(2k+1,1)(2k + 1)!= sen(x, 1).CAPITULO1. COEFICIENTEBINOMIAL 26 Corolario16. Daexpressaok=0(1)kx(2k+1,1)(2k + 1)!= sen(x, 1)aplicandoemrelacaoaxemamboslados,temosk=0(1)k x(2k+1,1)(2k + 1)!=k=0(1)k(2k + 1)x(2k,1)(2k + 1)(2k)!=k=0(1)kx(2k,1)(2k)!= sen(x, 1) == cos(x, 1) =2xcosx4assimk=0(1)k_ x2k_ = cos(x, 1)emanalogiacomaseriek=0(1)kx2k(2k)!= cosx.Exemplo15. Comotemosnk=0(1)k_ n2k_ =2ncosn4enk=0(1)k_n2k + 1_ =2nsenn4segue[nk=0(1)k_ n2k_]2+ [nk=0(1)k_n2k + 1_]2= 2nsen2n4+ 2ncos2n4= 2n.Exemplo16. Vamoscalcularnk=0_2n + 12k_ak.Temosqueessasomapodeserescritacomo2n+1k=0_2n + 1k_f(k)CAPITULO1. COEFICIENTEBINOMIAL 27onde f(k) =ak2se k par e f(k) =0se kmpar, tal func aopode ser escritacomof(k) = ak2_1 + (1)k2_etemos2n+1k=0_2n + 1k_f(k) =122n+1k=0_2n + 1k_ak2+122n+1k=0_2n + 1k_(a12)k=12(1+a12)2n+1+12(1a12)2n+1logonk=0_2n + 12k_ak=12(1 + a12)2n+1+12(1 a12)2n+1tomandoa = 1temosnk=0_2n + 12k_ =12(2)2n+1= 22n= 4n.Paracalcularnk=0_2n + 12k_kakpartimosdaidentidadenk=0_2n + 12k_ak=12(1 + a12)2n+1+12(1 a12)2n+1eaplicamosooperadoraD,datemosnk=0_2n + 12k_kak=2n + 14a12(1 + a12)2n2n + 14a12(1 a12)2ntomandoa = 1nk=0_2n + 12k_k =2n + 14(2)2n2n + 14(0)2nqueparan > 0cank=0_2n + 12k_k =2n + 14(2)2n.Lembrandodaidentidade(aD)pg(a) =pk=0_pk_akDkg(a)aplicandoemnk=0_2n + 12k_ak=12(1 + a12)2n+1+12(1 a12)2n+1CAPITULO1. COEFICIENTEBINOMIAL 28nk=0_2n + 12k_kpak=12pk=0_pk_akDk(1 + a12)2n+1+12pk=0_pk_akDk(1 a12)2n+11.5 ExercciosdotextoOs exerccios propostos aquiforamresolvidosnestetexto ouemtextosrelacionadoseservemtambemcomoumarevisaoderesultados.1.5.1 Propriedadesbasicas1. DemonstrearelacaodeStifel_p + 1k_ =_pk_ +_pk 1_usandoadenicaoporfatorialeporpotenciafatorial.2. Mostreque_2nn_en umeropar.3. Demonstreapropriedadedesimetria_np_ =_nn p_.4.(x + y)n=nk=0_nk_xkynk.5. Demonstreapropriedadedeabsorcao_nk_k + p=_n + pk + p_p1s=1(k + s)ps=1(n + s)6. Demonstreapropriedadedeabsorcaok(p,1)_nk_ = n(p,1)_n pk p_parapinteiroeparaprealusandoafunc aogamma.CAPITULO1. COEFICIENTEBINOMIAL 297.p_xk_ =_xk p_, k > p.8.p_xk_ = 0, p > k.9.p_xk_ = 1, p = k.10.(x + m)(n,1)=mk=0_mk_n(k,1)x(nk,1).11.xn=nk=0k!_xk__nk_.12._rk_ = (1)k_k r 1k_.13.ns=1_bs+1bs_ =bn+1!n+1k=1(ak)!ondebs=sk=1ak14._kp__nk_ =_np__n pk p_1.5.2 Somatorios1. Demonstreasseguintesidentidadesp_pk_ =_pk + 1_.2. Demonstrequenk=0k_nk_ = n2n1pordoismetodosdistintos.CAPITULO1. COEFICIENTEBINOMIAL 303.sp=a_pk_ =_s + 1k + 1__ak + 1_.4.sp=0_pk_ =_s + 1k + 1_.5.k_r + kk_ =_r + kk 1_.6.nk=0_r + kk_ =_r + n + 1n_.7. DemonstreaConvoluc aodeVandermondenk=0_rk__sn k_ =_r + sn_.8.np=0_np_2=_2nn_9. Demonstrededuasmaneirasdistintas2n=nk=0_nk_.10.nk=0_nk_k + p + 1=10xp(1 + x)ndx.11.nk=0_nk_k + 1=2n+11n + 1.12.nk=0ak+1_nk_k + 1=(1 + a)n+11n + 1.13.nk=0ak_nk_k + p + 1=pk=0p(k,1)xpk(1)ka(k+1)n(k1,1)(1 + ax)n+k+11x=0CAPITULO1. COEFICIENTEBINOMIAL 3114.nk=0(1)k_nk_k + 2=1(n + 1)(n + 2).15.nk=0ak_nk_k + 2=(1 + a)n+1(an + a 1)a2(n + 1)(n + 2).16.nk=0(1)k_nk_k + p + 1=(p + 1)(n + 1)(n + p + 2).17.nk=0_nk_ps=1(k + s)=_2n+pp1k=0_n + pk__1ps=1(n + s)18.nk=0k(p,1)_nk_ = n(p,1)2np.19.nk=0kp_nk_ =ps=0n(s,1)2ns_ps_20.nk=1(1)k1k(k + 1)_n + 1k_ =1 (n + 1)(1)nn + 2.21.nk=0_nk_coskx = 2n_cos(x2)_ncosnx2.22.nk=0_nk_senkx = 2n_cos(x2)_nsennx2.23.n1x=1xp=1p + 1pk=0Bk._p + 1k_np+1k24.x_xn_ax=nk=0_xn k_ak(1)kax(a 1)k+1CAPITULO1. COEFICIENTEBINOMIAL 3225.x_xn_Hx=_xn + 1_Hx _xn+1_n + 1.26.sx=0_xn_Hx=_s + 1n + 1_Hs+1 _s+1n+1_n + 1.27.bx=axn=nk=0k!_xk__nk_b+1a.28.nk=0_nk_(1)k= (0,n)29.nk=0_kp__nk_ =_np_2np.30.mk=0(1)k_nk_ =_mnm_.31.mk=0(1)k_nk_ = (1)m_n 1m_.32.kp=0_kp__np_=(n + 1)(n + 1 k).33.k=0_kp_xkk!=xpexp!.34. RegradeLeibnizparaderivadadoprodutoDn[f(x).g(x)] =nk=0[_nk_][Dnkf(x)].[Dkg(x)]35.k=0(1)k_ x2k_ = cos(x, 1)CAPITULO1. COEFICIENTEBINOMIAL 3336.k=0(1)k_x2k + 1_ = sen(x, 1).Comoteoremabinomial,podemosescreverumapotenciaxnnaformadesomasdotipo(x + a)kpoisxn= (a + x + a)n=nk=0_nk_(a)nk(x + a)k. Denicao 2(Coecientebinomialcentral). Chamamosocoecientebinomial_2nn_decoecientebinomialcentral. Propriedade10._2nn_einteiropar.Demonstracao. PelarelacaodeStiefeltemos_2nn_ =_2n 1n_+_2n 1n 1_poremtemos_2n 1n_ =(2n 1)!n!(2n 1 n)!=(2n 1)!n!(n 1)!=_2n 1n 1_ =(2n 1)!(n 1)!(2n 1 n + 1)!=(2n 1)!(n 1)!(n)!logo_2nn_ = 2_2n 1n_ = 2_2n 1n 1_.1.5.3 N umerosdeCatalan Denicao 3(N umerosdeCatalan). Paracadannaturaldenimoson umerocn=1n + 1_2nn_.Corolario 17.Os n umeros de Catalan sao naturais, pois vale que_2nn + 1_ =nn + 1_2nn_da(n + 1)_2nn + 1_ = n_2nn_comon + 1naodivideneledevedividir_2nn_.CAPITULO1. COEFICIENTEBINOMIAL 34Corolario18.Conclumos assim que o coeciente binomial central e sempre m ultiplode2eden + 1.Exemplo17(ITA-2001-Questao7-Resolvida). Adiferenca_2nn__2nn 1_ =(2n)!n!2(2n)!(n 1)!(n + 1)!=(2n)!n!2(1 nn + 1) ==_2nn_1n + 1.Essa e tambem uma maneira de provar que o n umero de Catalan_2nn_1n + 1e natural. Propriedade11. Valequenk=0(1)kck_n + kn k_ = 0n.Demonstracao. Escrevemosck_n + kn k_ =(2k)!k!k!(k + 1)(n + k)!(n k)!(2k)!=1(n + 1)!(n + k)!k!n!(n + 1)!(n k)!(k + 1)!==1n + 1_n + 1n k__n + kk_agora(1)k_n + kk_ =_k n k 1k_ =_n 1k_daasomacacomo1n + 1nk=0_n 1k__n + 1n k_ =_0n_n + 1pelaconvolu caodeVandermonde.Exemplo18. Mostreque1n + 1nk=1(4 2k)eumn umeronaturalparaqualquern.CAPITULO1. COEFICIENTEBINOMIAL 35Temosque1n + 1nk=1(4 2k) =2nn + 1nk=1(2k 1)k=2n(2n)!(n + 1)2n.n!.n!=1n + 1_2nn_.Ondeusamosoresultadodoprodutodos mparesnk=1(2k 1) =(2n)!2n.n!1.6 Coecientebinomialen umerosdeFibonacci Propriedade12(Coecientebinomialen umerosdeFibonacci).nk=0_n kk_ = F(n + 1).Essapropriedaderelacionasomadecoecientesbinomiaiscomasequenciadebonacci. Demonstracao. Vamos provar que tal soma binomial satisfaz as condic oes iniciaisdasequenciadebonaccieasuarecorrencia. Sejaent aog(n + 1) =nk=0_n kk_.Temos0k=0_0 kk_ =_00_ = 1 = F(1) = G(1)1k=0_1 kk_ =_10_ +_01_ = 1 = F(2) = G(2)logoascondic oesiniciaisforamvericadas,tem-seaindag(n + 2) =n+1k=0_n + 1 kk_ =nk=0_n + 1 kk_ +_0n + 1_ =nk=0_n + 1 kk_logog(n + 2) + g(n + 1) =nk=0_n + 1 kk_+_n kk_vamosmostrarquetalsoma eg(n + 3)g(n + 3) =n+2k=0_n + 2 kk_ =n+1k=0_n + 2 kk_ +_0n + 2_ =n+1k=0_n + 2 kk_ =CAPITULO1. COEFICIENTEBINOMIAL 36aplicandoarelac aodestifel,segue=n+1k=0_n + 1 kk_+n+1k=0_n + 1 kk 1_ =nk=0_n + 1 kk_+_0n + 1_+n+1k=1_n + 1 kk 1_ ==nk=0_n + 1 kk_ +nk=0_n kk_ = g(n + 2) + g(n + 1)logovaleF(n) = g(n) . Propriedade13.nk=0_nk_F(k) = F(2n).Demonstracao. Sejag(n) =nk=0_nk_F(k)comosabemosqueasequenciadebonaccisatisfazarecorrenciaF(n + 2) = F(n + 1) +F(n), (E2E1)F(n) = 0, logo a recorrencia que g(n) satisfaz e (21)g(n), mas(21) = (E23E +1) basta usar = E 1 e expandir para ver essa identidade,dag(n)satisfazarecorrenciag(n + 2)=3g(n + 1) g(n),umarecorrenciadesegundaordemprecisadeduascondic oesiniciais,tomandoentaog(0) =0k=0_nk_F(k) =_00_F(0) = 0 = F(0)g(1) =1k=0_1k_F(k) =_10_F(0) +_11_F(1) = 1 = F(2)mostraremos agoraque h(n) =F(2n) satisfaz amesmarecorrenciade g(n) da ademonstracaoestaraterminadaF(2n + 2) = F(2n) + F(2n + 1) F(2n + 1) = F(2n + 2) F(2n)somandoF(2n + 2)aosdoisladossegue F(2n + 2) + F(2n + 1) = 2F(2n + 2) F(2n)comoF(2n + 3) = F(2n + 2) + F(2n + 1)segueF(2n + 3) = 2F(2n + 2) F(2n)CAPITULO1. COEFICIENTEBINOMIAL 37somandoF(2n + 2)aosdoisladossegueF(2n + 3) + F(2n + 2) = 3F(2n + 2) F(2n)mascomoF(2n + 3) + F(2n + 2) = F(2n + 4)seguenalmentequeF(2n + 4) = 3F(2n + 2) F(2n) . Corolario19.nk=0_nk_F(k + 1) = F(2n + 1)poisF(2n) =nk=0_nk_F(k + 1) = F(2n + 2) F(2n)mascomovaleF(2n + 2) = F(2n) + F(2n + 1)segueF(2n + 2) F(2n) = F(2n + 1). Propriedade14.nk=0_nk_F(k + p) = F(2n + p)parapnatural.Demonstracao. Vamosprovarporinduc aoquepF(2n)=F(2n + p). Parap=0aidentidadeeverdadeira, supondoavalidadeparap: pF(2n) =F(2n + p),vamos provar para p +1: p+1F(2n) = F(2n +p +1) .Como vale pF(2n) = F(2n +p),aplicamosemambosladosp+1F(2n) = F(2n + p) = F(2n + p + 2) F(2n + p)mas F(2n+p+2) = F(2n+p)+F(2n+p+1) da F(2n+p+2)F(2n+p) = F(2n+p+1)deondeseguep+1F(2n) = F(2n + p + 1)logoestaprovadaapropriedade.PartindodaidentidadeF(2n) =nk=0_nk_F(k)aplicamosp,dapF(2n) = F(2n + p) =nk=0_nk_F(k + p).CAPITULO1. COEFICIENTEBINOMIAL 38 Corolario20. Daidentidadesl=0_s ll_ = F(s + 1)substituindospork + p 1seguek+p1l=0_k + p 1 ll_ = F(k + p)multiplicandopor_nk_etomandoasomacomkvariandodek = 0aten,seguenk=0k+p1l=0_k + p 1 ll__nk_ =nk=0_nk_F(k + p) = F(2n + p)logonk=0k+p1l=0_k + p 1 ll__nk_ = F(2n + p).1.7 CrescimentoeDescrescimentodocoecientebi-nomialVamosanalisarquandoocoecientebinomial cresceequandodecresceparaumnu-meradorxoneumdenominadorquevaria0 k n. Propriedade15(Crescimento)._nk + 1_ >_nk_paran 12> k.Demonstracao._nk + 1_ >_nk_,n(k+1,1)(k + 1)k!>n(k,1)k!podemoscancelarosfatoresk! nodenominadorpoisk! >0, abriraprimeirapotenciafatorialn(k+1,1)= n(k,1)(n k)candon(k,1)(n k)(k + 1)> n(k,1)CAPITULO1. COEFICIENTEBINOMIAL 39podemoscancelarotermocomumn(k,1)pois emaiorquezero,dasegue(n k)(k + 1)> 1, n k > k + 1, n 1 > 2k,n 12> k.Entaoocoecientebinomialiracrescerparak