Sequencias e Somatorios - Matematica Discreta

Sequˆencias e Somatorios QXD0008 Matematica Discreta Prof Lucas Ismaily ismailybfufcbr Universidade Federal do Ceara 1º semestre2024 Topicos desta aula Nesta apresentacao Sequˆencias PA PG Relacoes de Recorrˆencia Somatorios Propriedades Mudanca de Indice 2 Referˆencias para esta aula Esta aula foi baseada na seguinte secao Secao 24 do livro Discrete Mathematics and Its Applications Author Kenneth H Rosen Seventh Edition English version Uma versao mais resumida do conteudo pode ser encontrada tambem nesta secao Secao 24 do livro Matematica Discreta e suas Aplicacoes Autor Kenneth H Rosen Sexta Edicao 3 Introdução Sequˆencia Definicao Definicao Uma sequˆencia e uma funcao de um subconjunto dos inteiros para um conjunto S qualquer Dada uma sequˆencia Seu domınio e um subconjunto dos inteiros Comumente usase D 0 1 2 ou D 1 2 3 O domınio de uma sequˆencia tambem e chamado de ındice Seu contradomınio pode ser qualquer conjunto Constatacao Toda funcao f D S tal que D Z e uma sequˆencia 5 Sequˆencia Definicao Definicao Uma sequˆencia e uma funcao de um subconjunto dos inteiros para um conjunto S qualquer Dada uma sequˆencia Seu domınio e um subconjunto dos inteiros Comumente usase D 0 1 2 ou D 1 2 3 O domınio de uma sequˆencia tambem e chamado de ındice Seu contradomınio pode ser qualquer conjunto Constatacao Toda funcao f D S tal que D Z e uma sequˆencia 5 Sequˆencia Definicao Definicao Uma sequˆencia e uma funcao de um subconjunto dos inteiros para um conjunto S qualquer Dada uma sequˆencia Seu domınio e um subconjunto dos inteiros Comumente usase D 0 1 2 ou D 1 2 3 O domınio de uma sequˆencia tambem e chamado de ındice Seu contradomınio pode ser qualquer conjunto Constatacao Toda funcao f D S tal que D Z e uma sequˆencia 5 Sequˆencia Definicao Definicao Uma sequˆencia e uma funcao de um subconjunto dos inteiros para um conjunto S qualquer Dada uma sequˆencia Seu domınio e um subconjunto dos inteiros Comumente usase D 0 1 2 ou D 1 2 3 O domınio de uma sequˆencia tambem e chamado de ındice Seu contradomınio pode ser qualquer conjunto Constatacao Toda funcao f D S tal que D Z e uma sequˆencia 5 Sequˆencia Exemplo Definicao Uma sequˆencia e uma funcao de um subconjunto dos inteiros para um conjunto S qualquer Exemplo A funcao f n 2n com domınio restrito aos naturais Neste caso temos f N N com f n 2n f 0 1 f 1 2 f 2 4 f 3 8 f 4 16 f 5 32 f 6 64 f 7 128 f 8 256 Em algumas situacoes falaremos simplesmente da sequˆencia 1 2 4 8 16 32 64 128 256 6 Sequˆencia Exemplo Definicao Uma sequˆencia e uma funcao de um subconjunto dos inteiros para um conjunto S qualquer Exemplo A funcao f n 2n com domınio restrito aos naturais Neste caso temos f N N com f n 2n f 0 1 f 1 2 f 2 4 f 3 8 f 4 16 f 5 32 f 6 64 f 7 128 f 8 256 Em algumas situacoes falaremos simplesmente da sequˆencia 1 2 4 8 16 32 64 128 256 6 Sequˆencia Exemplo Definicao Uma sequˆencia e uma funcao de um subconjunto dos inteiros para um conjunto S qualquer Exemplo A funcao f n 2n com domınio restrito aos naturais Neste caso temos f N N com f n 2n f 0 1 f 1 2 f 2 4 f 3 8 f 4 16 f 5 32 f 6 64 f 7 128 f 8 256 Em algumas situacoes falaremos simplesmente da sequˆencia 1 2 4 8 16 32 64 128 256 6 Sequˆencia Notacao Notacao Opcoes a funcao f n 2n com domınio restrito aos naturais a sequˆencia 1 2 4 8 16 32 64 128 256 a sequˆencia an com an 2n Exemplo Considere a sequˆencia an com an 1 n Quem sao os termos de an Ou seja quem sao a1 a2 a3 a4 Resposta a1 1 a2 1 2 a3 1 3 a4 1 4 Alternativamente a sequˆencia e 1 1 2 1 3 1 4 7 Sequˆencia Notacao Notacao Opcoes a funcao f n 2n com domınio restrito aos naturais a sequˆencia 1 2 4 8 16 32 64 128 256 a sequˆencia an com an 2n Exemplo Considere a sequˆencia an com an 1 n Quem sao os termos de an Ou seja quem sao a1 a2 a3 a4 Resposta a1 1 a2 1 2 a3 1 3 a4 1 4 Alternativamente a sequˆencia e 1 1 2 1 3 1 4 7 Sequˆencia Notacao Notacao Opcoes a funcao f n 2n com domınio restrito aos naturais a sequˆencia 1 2 4 8 16 32 64 128 256 a sequˆencia an com an 2n Exemplo Considere a sequˆencia an com an 1 n Quem sao os termos de an Ou seja quem sao a1 a2 a3 a4 Resposta a1 1 a2 1 2 a3 1 3 a4 1 4 Alternativamente a sequˆencia e 1 1 2 1 3 1 4 7 Sequˆencia Notacao Notacao Opcoes a funcao f n 2n com domınio restrito aos naturais a sequˆencia 1 2 4 8 16 32 64 128 256 a sequˆencia an com an 2n Exemplo Considere a sequˆencia an com an 1 n Quem sao os termos de an Ou seja quem sao a1 a2 a3 a4 Resposta a1 1 a2 1 2 a3 1 3 a4 1 4 Alternativamente a sequˆencia e 1 1 2 1 3 1 4 7 Sequˆencia Notacao Notacao Opcoes a funcao f n 2n com domınio restrito aos naturais a sequˆencia 1 2 4 8 16 32 64 128 256 a sequˆencia an com an 2n Exemplo Considere a sequˆencia an com an 1 n Quem sao os termos de an Ou seja quem sao a1 a2 a3 a4 Resposta a1 1 a2 1 2 a3 1 3 a4 1 4 Alternativamente a sequˆencia e 1 1 2 1 3 1 4 7 Progressão Aritmética Progressao Aritmetica Definicao Definicao Uma progressao aritmetica PA e uma sequˆencia da forma a0 a0 d a0 2d a0 3d a0 nd onde a0 e d sao numeros reais Dada uma PA a0 e o seu termo inicial d e sua razao aritmetica ou diferenca comum 9 Progressao Aritmetica REPARE Os termos de uma sequˆencia comum seriam a0 a1 a2 a3 Os termos descritos na PA sao a0 a0 d a0 2d a0 3d a0 0d a0 1d a0 2d a0 3d a0 nd a0 a1 a2 a3 an Constatacao Cada PA e caracterizada por uma funcao da forma f x a0 dx onde a0 e d sao numeros reais mas com domınio restrito a um subconjunto dos inteiros Dizemos ainda que a PA a0 a0 d a0 2d a0 3d a0 nd e a analoga discreta da funcao linear f x a0 dx 10 Progressao Aritmetica REPARE Os termos de uma sequˆencia comum seriam a0 a1 a2 a3 Os termos descritos na PA sao a0 a0 d a0 2d a0 3d a0 0d a0 1d a0 2d a0 3d a0 nd a0 a1 a2 a3 an Constatacao Cada PA e caracterizada por uma funcao da forma f x a0 dx onde a0 e d sao numeros reais mas com domınio restrito a um subconjunto dos inteiros Dizemos ainda que a PA a0 a0 d a0 2d a0 3d a0 nd e a analoga discreta da funcao linear f x a0 dx 10 Progressao Aritmetica REPARE Os termos de uma sequˆencia comum seriam a0 a1 a2 a3 Os termos descritos na PA sao a0 a0 d a0 2d a0 3d a0 0d a0 1d a0 2d a0 3d a0 nd a0 a1 a2 a3 an Constatacao Cada PA e caracterizada por uma funcao da forma f x a0 dx onde a0 e d sao numeros reais mas com domınio restrito a um subconjunto dos inteiros Dizemos ainda que a PA a0 a0 d a0 2d a0 3d a0 nd e a analoga discreta da funcao linear f x a0 dx 10 Progressao Aritmetica Exemplo A sequˆencia sn com sn 1 4n e uma progressao aritmetica Perguntas 1 Qual o primeiro termo da lista 2 Qual a razao aritmetica da PA 3 Quem sao os primeiros cinco termos 11 Progressao Aritmetica Exemplo A sequˆencia sn com sn 1 4n e uma progressao aritmetica Perguntas 1 Qual o primeiro termo da lista s0 1 4 0 1 2 Qual a razao aritmetica da PA d 4 3 Quem sao os primeiros cinco termos 1 3 7 11 15 11 Progressao Aritmetica Exemplo A sequˆencia sn com sn 1 4n e uma progressao aritmetica Perguntas 1 Qual o primeiro termo da lista s0 1 4 0 1 2 Qual a razao aritmetica da PA d 4 3 Quem sao os primeiros cinco termos 1 3 7 11 15 Observacao Dizemos que esta sequˆencia e infinita e crescente 11 Progressao Aritmetica Exercıcio para casa Prove o seguinte teorema Teorema Para todo n N e a d R a a d a 2d a n 1d n2a n 1d 2 12 Progressão Geométrica Progressao Geometrica Definicao Definicao Uma progressao geometrica PG e uma sequˆencia da forma a0 a0r a0r 2 a0r 3 a0r n onde a0 e r sao numeros reais Dada uma PG a0 e o seu termo inicial r e sua razao geometrica ou razao comum 14 Progressao Geometrica REPARE Os termos de uma sequˆencia comum seriam a0 a1 a2 a3 Os termos descritos na PA sao a0 a0r a0r 2 a0r 3 a0r 0 a0r 1 a0r 2 a0r 3 a0r n a0 a1 a2 a3 an Constatacao Cada PG e caracterizada por uma funcao da forma f x a0r x onde a0 e r sao numeros reais mas com domınio restrito a um subconjunto dos inteiros Dizemos ainda que a PG a0 a0r a0r 2 a0r 3 a0r n e a analoga discreta da funcao exponencial f x a0r x 15 Progressao Geometrica REPARE Os termos de uma sequˆencia comum seriam a0 a1 a2 a3 Os termos descritos na PA sao a0 a0r a0r 2 a0r 3 a0r 0 a0r 1 a0r 2 a0r 3 a0r n a0 a1 a2 a3 an Constatacao Cada PG e caracterizada por uma funcao da forma f x a0r x onde a0 e r sao numeros reais mas com domınio restrito a um subconjunto dos inteiros Dizemos ainda que a PG a0 a0r a0r 2 a0r 3 a0r n e a analoga discreta da funcao exponencial f x a0r x 15 Progressao Geometrica REPARE Os termos de uma sequˆencia comum seriam a0 a1 a2 a3 Os termos descritos na PA sao a0 a0r a0r 2 a0r 3 a0r 0 a0r 1 a0r 2 a0r 3 a0r n a0 a1 a2 a3 an Constatacao Cada PG e caracterizada por uma funcao da forma f x a0r x onde a0 e r sao numeros reais mas com domınio restrito a um subconjunto dos inteiros Dizemos ainda que a PG a0 a0r a0r 2 a0r 3 a0r n e a analoga discreta da funcao exponencial f x a0r x 15 Progressao Geometrica Exemplo A sequˆencia cn com cn 2 5n e uma progressao geometrica Perguntas 1 Qual o primeiro termo da lista 2 Qual a razao geometrica da PG 3 Quem sao os primeiros cinco termos 16 Progressao Geometrica Exemplo A sequˆencia cn com cn 2 5n e uma progressao geometrica Perguntas 1 Qual o primeiro termo da lista c0 2 50 2 1 2 2 Qual a razao geometrica da PG r 5 3 Quem sao os primeiros cinco termos 2 10 50 250 1250 16 Progressao Geometrica Exemplo A sequˆencia cn com cn 2 5n e uma progressao geometrica Perguntas 1 Qual o primeiro termo da lista c0 2 50 2 1 2 2 Qual a razao geometrica da PG r 5 3 Quem sao os primeiros cinco termos 2 10 50 250 1250 Observacao Dizemos que esta sequˆencia e infinita e crescente 16 Progressão Geométrica Exemplo A sequência dn com dn 6 13n é uma progressão geométrica Perguntas 1 Qual o primeiro termo da lista 2 Qual a razão geométrica da PG 3 Quem são os primeiros cinco termos Progressão Geométrica Exemplo A sequência dn com dn 6 13n é uma progressão geométrica Perguntas 1 Qual o primeiro termo da lista d0 6 130 6 1 6 2 Qual a razão geométrica da PG r 13 3 Quem são os primeiros cinco termos 6 2 23 29 227 Progressão Geométrica Exemplo A sequência dn com dn 6 13n é uma progressão geométrica Perguntas 1 Qual o primeiro termo da lista d0 6 130 6 1 6 2 Qual a razão geométrica da PG r 13 3 Quem são os primeiros cinco termos 6 2 23 29 227 Observação Dizemos que esta sequência é infinita e decrescente Progressao Geometrica Exemplo A sequˆencia en com en 1n e uma progressao geometrica Perguntas 1 Qual o primeiro termo da lista 2 Qual a razao geometrica da PG 3 Quem sao os primeiros cinco termos 18 Progressao Geometrica Exemplo A sequˆencia en com en 1n e uma progressao geometrica Perguntas 1 Qual o primeiro termo da lista e0 10 1 2 Qual a razao geometrica da PG r 1 3 Quem sao os primeiros cinco termos 1 1 1 1 1 18 Progressao Geometrica Exemplo A sequˆencia en com en 1n e uma progressao geometrica Perguntas 1 Qual o primeiro termo da lista e0 10 1 2 Qual a razao geometrica da PG r 1 3 Quem sao os primeiros cinco termos 1 1 1 1 1 Se uma sequˆencia e sempre crescente ou sempre decrescente ela e chamada de monotona Observacao Dizemos que esta sequˆencia e infinita e nao monotona 18 Somas de Progressoes Geometricas Teorema Para todo n N e a r R com r 1 temse que a ar ar 2 ar n ar n1 a r 1 Demonstracao Seja Pn a afirmacao de que a soma dos n 1 primeiros termos de uma progressao geometrica e ar n1a r1 Vamos provar por inducao em n Base P0 e verdadeiro pois ar 01 a r 1 ar a r 1 ar 1 r 1 a 19 Somas de Progressoes Geometricas Teorema Para todo n N e a r R com r 1 temse que a ar ar 2 ar n ar n1 a r 1 Demonstracao Seja Pn a afirmacao de que a soma dos n 1 primeiros termos de uma progressao geometrica e ar n1a r1 Vamos provar por inducao em n Base P0 e verdadeiro pois ar 01 a r 1 ar a r 1 ar 1 r 1 a 19 Somas de Progressoes Geometricas Teorema Para todo n N e a r R com r 1 temse que a ar ar 2 ar n ar n1 a r 1 Demonstracao Seja Pn a afirmacao de que a soma dos n 1 primeiros termos de uma progressao geometrica e ar n1a r1 Vamos provar por inducao em n Base P0 e verdadeiro pois ar 01 a r 1 ar a r 1 ar 1 r 1 a 19 Somas de Progressoes Geometricas Teorema Para todo n N e a r R com r 1 temse que a ar ar 2 ar n ar n1 a r 1 Demonstracao Seja Pn a afirmacao de que a soma dos n 1 primeiros termos de uma progressao geometrica e ar n1a r1 Vamos provar por inducao em n Base P0 e verdadeiro pois ar 01 a r 1 ar a r 1 ar 1 r 1 a 19 Somas de Progressoes Geometricas Teorema Para todo n N e r R com r 1 temse que a ar ar 2 ar n ar n1 a r 1 Continuacao da Demonstracao Passo Indutivo A Hipotese de Inducao e a afirmacao de que Pk e verdadeiro para um natural k arbitrario Ou seja Pk e a afirmacao a ar ar 2 ar k ar k1 a r 1 Devemos mostrar que se Pk e verdadeiro entao Pk 1 e verdadeiro Ou seja devemos mostrar que a ar ar 2 ar k ar k1 ar k2 a r 1 20 Somas de Progressoes Geometricas Teorema Para todo n N e r R com r 1 temse que a ar ar 2 ar n ar n1 a r 1 Continuacao da Demonstracao Passo Indutivo A Hipotese de Inducao e a afirmacao de que Pk e verdadeiro para um natural k arbitrario Ou seja Pk e a afirmacao a ar ar 2 ar k ar k1 a r 1 Devemos mostrar que se Pk e verdadeiro entao Pk 1 e verdadeiro Ou seja devemos mostrar que a ar ar 2 ar k ar k1 ar k2 a r 1 20 Somas de Progressoes Geometricas Teorema Para todo n N e r R com r 1 temse que a ar ar 2 ar n ar n1 a r 1 Continuacao da Demonstracao Passo Indutivo A Hipotese de Inducao e a afirmacao de que Pk e verdadeiro para um natural k arbitrario Ou seja Pk e a afirmacao a ar ar 2 ar k ar k1 a r 1 Devemos mostrar que se Pk e verdadeiro entao Pk 1 e verdadeiro Ou seja devemos mostrar que a ar ar 2 ar k ar k1 ar k2 a r 1 20 Somas de Progressoes Geometricas Teorema Para todo n N e r R com r 1 temse que a ar ar 2 ar n ar n1 a r 1 Continuacao da Demonstracao Passo Indutivo A Hipotese de Inducao e a afirmacao de que Pk e verdadeiro para um natural k arbitrario Ou seja Pk e a afirmacao a ar ar 2 ar k ar k1 a r 1 Devemos mostrar que se Pk e verdadeiro entao Pk 1 e verdadeiro Ou seja devemos mostrar que a ar ar 2 ar k ar k1 ar k2 a r 1 20 Somas de Progressões Geométricas Teorema Para todo n N e r R com r 1 temse que a ar ar2 arn arn1 a r 1 Continuação da Demonstração a ar ar2 ark ark1 Oportunidade de aplicar a HI Somas de Progressões Geométricas Teorema Para todo n N e r R com r 1 temse que a ar ar2 arn arn1 a r 1 Continuação da Demonstração a ar ar2 ark ark1 HI ark1 a r 1 ark1 Oportunidade de aplicar a HI Somas de Progressões Geométricas Teorema Para todo n N e r R com r 1 temse que a ar ar2 arn arn1 a r 1 Continuação da Demonstração a ar ar2 ark ark1 HI ark1 a r 1 ark1 ark1 a r 1 ark2 ark1 r 1 Somas de Progressões Geométricas Teorema Para todo n N e r R com r 1 temse que a ar ar2 arn arn1 a r 1 Continuação da Demonstração a ar ar2 ark ark1 HI ark1 a r 1 ark1 Oportunidade de aplicar a HI ark1 a r 1 ark2 ark1 r 1 ark2 a r 1 Isso mostra que se a hipótese de indução Pk for verdadeira então Pk 1 também é verdadeira Isso completa a prova do passo indutivo Como provamos a base e o passo indutivo a prova por indução está completa 21 Relações de Recorrência 22 Outras formas de especificar sequˆencias Vimos que PAs e PGs podem ser especificadas fornecendo formulas explıcitas para seus termos PA an a0 n d PG cn c0 r n Porem existem outros modos de especificar uma sequˆencia Uma outra forma consiste em fornecer um ou mais termos iniciais juntamente com uma regra de formacao dos termos subsequentes 23 Outras formas de especificar sequˆencias Vimos que PAs e PGs podem ser especificadas fornecendo formulas explıcitas para seus termos PA an a0 n d PG cn c0 r n Porem existem outros modos de especificar uma sequˆencia Uma outra forma consiste em fornecer um ou mais termos iniciais juntamente com uma regra de formacao dos termos subsequentes 23 Relacoes de Recorrˆencia Definicao Uma relacao de recorrˆencia para a sequˆencia an e uma equacao que expressa cada termo an em funcao de um ou mais termos que o antecedem Dizemos que uma sequˆencia resolve uma relacao de recorrˆencia se seus termos satisfazem a relacao de recorrˆencia Exemplo Seja an a sequˆencia que satisfaz a relacao de recorrˆencia an an1 3 para todo n 1 em que a0 2 Tambem e comum especificar uma relacao de recorrˆencia utilizando a letra T nesse caso temse que Tn Tn 1 3 sendo T0 2 Pergunta Quais sao os termos T1 T2 e T3 T1 T0 3 2 3 5 T2 T1 3 5 3 8 T3 T2 3 8 3 11 Veja que foi necessario calcular algum termo novo antes de cada Tn 24 Relacoes de Recorrˆencia Definicao Uma relacao de recorrˆencia para a sequˆencia an e uma equacao que expressa cada termo an em funcao de um ou mais termos que o antecedem Dizemos que uma sequˆencia resolve uma relacao de recorrˆencia se seus termos satisfazem a relacao de recorrˆencia Exemplo Seja an a sequˆencia que satisfaz a relacao de recorrˆencia an an1 3 para todo n 1 em que a0 2 Tambem e comum especificar uma relacao de recorrˆencia utilizando a letra T nesse caso temse que Tn Tn 1 3 sendo T0 2 Pergunta Quais sao os termos T1 T2 e T3 T1 T0 3 2 3 5 T2 T1 3 5 3 8 T3 T2 3 8 3 11 Veja que foi necessario calcular algum termo novo antes de cada Tn 24 Relacoes de Recorrˆencia Definicao Uma relacao de recorrˆencia para a sequˆencia an e uma equacao que expressa cada termo an em funcao de um ou mais termos que o antecedem Dizemos que uma sequˆencia resolve uma relacao de recorrˆencia se seus termos satisfazem a relacao de recorrˆencia Exemplo Seja an a sequˆencia que satisfaz a relacao de recorrˆencia an an1 3 para todo n 1 em que a0 2 Tambem e comum especificar uma relacao de recorrˆencia utilizando a letra T nesse caso temse que Tn Tn 1 3 sendo T0 2 Pergunta Quais sao os termos T1 T2 e T3 T1 T0 3 2 3 5 T2 T1 3 5 3 8 T3 T2 3 8 3 11 Veja que foi necessario calcular algum termo novo antes de cada Tn 24 Relacoes de Recorrˆencia Definicao Uma relacao de recorrˆencia para a sequˆencia an e uma equacao que expressa cada termo an em funcao de um ou mais termos que o antecedem Dizemos que uma sequˆencia resolve uma relacao de recorrˆencia se seus termos satisfazem a relacao de recorrˆencia Exemplo Seja an a sequˆencia que satisfaz a relacao de recorrˆencia an an1 3 para todo n 1 em que a0 2 Tambem e comum especificar uma relacao de recorrˆencia utilizando a letra T nesse caso temse que Tn Tn 1 3 sendo T0 2 Pergunta Quais sao os termos T1 T2 e T3 T1 T0 3 2 3 5 T2 T1 3 5 3 8 T3 T2 3 8 3 11 Veja que foi necessario calcular algum termo novo antes de cada Tn 24 Relacoes de Recorrˆencia Definicao Uma relacao de recorrˆencia para a sequˆencia an e uma equacao que expressa cada termo an em funcao de um ou mais termos que o antecedem Dizemos que uma sequˆencia resolve uma relacao de recorrˆencia se seus termos satisfazem a relacao de recorrˆencia Exemplo Seja an a sequˆencia que satisfaz a relacao de recorrˆencia an an1 3 para todo n 1 em que a0 2 Tambem e comum especificar uma relacao de recorrˆencia utilizando a letra T nesse caso temse que Tn Tn 1 3 sendo T0 2 Pergunta Quais sao os termos T1 T2 e T3 T1 T0 3 2 3 5 T2 T1 3 5 3 8 T3 T2 3 8 3 11 Veja que foi necessario calcular algum termo novo antes de cada Tn 24 Relacoes de Recorrˆencia Definicao Uma relacao de recorrˆencia para a sequˆencia an e uma equacao que expressa cada termo an em funcao de um ou mais termos que o antecedem Dizemos que uma sequˆencia resolve uma relacao de recorrˆencia se seus termos satisfazem a relacao de recorrˆencia Exemplo Seja an a sequˆencia que satisfaz a relacao de recorrˆencia an an1 3 para todo n 1 em que a0 2 Tambem e comum especificar uma relacao de recorrˆencia utilizando a letra T nesse caso temse que Tn Tn 1 3 sendo T0 2 Pergunta Quais sao os termos T1 T2 e T3 T1 T0 3 2 3 5 T2 T1 3 5 3 8 T3 T2 3 8 3 11 Veja que foi necessario calcular algum termo novo antes de cada Tn 24 Relacoes de Recorrˆencia Exemplo Exemplo Seja an a sequˆencia que satisfaz a relacao de recorrˆencia an 3 se n 0 5 se n 1 an1 an2 se n 2 Pergunta Quais sao os termos a2 a3 a4 a2 a1 a0 5 3 2 a3 a2 a1 2 5 3 a4 a3 a2 3 2 5 an e a sequˆencia 3 5 2 3 5 2 3 5 25 Relacoes de Recorrˆencia Exemplo Exemplo Seja an a sequˆencia que satisfaz a relacao de recorrˆencia an 3 se n 0 5 se n 1 an1 an2 se n 2 Pergunta Quais sao os termos a2 a3 a4 a2 a1 a0 5 3 2 a3 a2 a1 2 5 3 a4 a3 a2 3 2 5 an e a sequˆencia 3 5 2 3 5 2 3 5 25 Relacoes de Recorrˆencia Exemplo Exemplo Seja an a sequˆencia que satisfaz a relacao de recorrˆencia an 3 se n 0 5 se n 1 an1 an2 se n 2 Pergunta Quais sao os termos a2 a3 a4 a2 a1 a0 5 3 2 a3 a2 a1 2 5 3 a4 a3 a2 3 2 5 an e a sequˆencia 3 5 2 3 5 2 3 5 25 Relacoes de Recorrˆencia Exemplo Exemplo Seja an a sequˆencia que satisfaz a relacao de recorrˆencia an 3 se n 0 5 se n 1 an1 an2 se n 2 Pergunta Quais sao os termos a2 a3 a4 a2 a1 a0 5 3 2 a3 a2 a1 2 5 3 a4 a3 a2 3 2 5 an e a sequˆencia 3 5 2 3 5 2 3 5 25 Exemplo Sequˆencia de Fibonacci Definicao A sequˆencia de Fibonacci e definida pela relacao de recorrˆencia fn 0 se n 0 1 se n 1 fn1 fn2 se n 2 Leonardo Fibonacci Pergunta Quais sao os numeros f2 f3 f4 f5 f6 f2 f1 f0 1 0 1 f3 f2 f1 1 1 2 f4 f3 f2 2 1 3 f5 f4 f3 3 2 5 f6 f5 f4 5 3 8 26 Exemplo Sequˆencia de Fibonacci Definicao A sequˆencia de Fibonacci e definida pela relacao de recorrˆencia fn 0 se n 0 1 se n 1 fn1 fn2 se n 2 Leonardo Fibonacci Pergunta Quais sao os numeros f2 f3 f4 f5 f6 f2 f1 f0 1 0 1 f3 f2 f1 1 1 2 f4 f3 f2 2 1 3 f5 f4 f3 3 2 5 f6 f5 f4 5 3 8 26 Exemplo Sequˆencia de Fibonacci Definicao A sequˆencia de Fibonacci e definida pela relacao de recorrˆencia fn 0 se n 0 1 se n 1 fn1 fn2 se n 2 Leonardo Fibonacci Pergunta Quais sao os numeros f2 f3 f4 f5 f6 f2 f1 f0 1 0 1 f3 f2 f1 1 1 2 f4 f3 f2 2 1 3 f5 f4 f3 3 2 5 f6 f5 f4 5 3 8 26 Exemplo Sequˆencia de Fibonacci Definicao A sequˆencia de Fibonacci e definida pela relacao de recorrˆencia fn 0 se n 0 1 se n 1 fn1 fn2 se n 2 Leonardo Fibonacci Pergunta Quais sao os numeros f2 f3 f4 f5 f6 f2 f1 f0 1 0 1 f3 f2 f1 1 1 2 f4 f3 f2 2 1 3 f5 f4 f3 3 2 5 f6 f5 f4 5 3 8 26 Resolvendo relacoes de recorrˆencia 27 Resolvendo Relações de Recorrência Definição Dizemos que resolvemos uma relação de recorrência quando encontramos uma fórmula explícita para os termos da sequência Essa fórmula explícita é chamada fórmula fechada 28 Resolvendo Relações de Recorrência Definição Dizemos que resolvemos uma relação de recorrência quando encontramos uma fórmula explícita para os termos da sequência Essa fórmula explícita é chamada fórmula fechada Exemplo Anteriormente vimos a sequência de fibonacci fn definida recursivamente por f0 0 f1 1 e para n 2 fn fn1 fn2 Resolvendo Relações de Recorrência Definição Dizemos que resolvemos uma relação de recorrência quando encontramos uma fórmula explícita para os termos da sequência Essa fórmula explícita é chamada fórmula fechada Exemplo Anteriormente vimos a sequência de fibonacci fn definida recursivamente por f0 0 f1 1 e para n 2 fn fn1 fn2 Problema Para n grande o cálculo de fn pode ser muito tedioso Seria bom se existisse uma fórmula fechada para os termos dessa sequência Resolvendo Relações de Recorrência Definição Dizemos que resolvemos uma relação de recorrência quando encontramos uma fórmula explícita para os termos da sequência Essa fórmula explícita é chamada fórmula fechada Exemplo Anteriormente vimos a sequência de fibonacci fn definida recursivamente por f0 0 f1 1 e para n 2 fn fn1 fn2 Problema Para n grande o cálculo de fn pode ser muito tedioso Seria bom se existisse uma fórmula fechada para os termos dessa sequência Felizmente existe uma fórmula fechada para esta sequência Para n 1 temos que fn 1 5 1 5 2 n 1 5 2 n Metodo da substituicao iterativo Existem diversos metodos para resolver relacoes de recorrˆencia Um metodo simples e o metodo da substituicao iterativo Nesta tecnica usamos repetidamente a relacao de recorrˆencia para expandir a expressao para o nesimo termo ate poder ter uma ideia da forma geral uma conjectura Logo apos esta conjectura e verificada por inducao matematica 29 Metodo da substituicao iterativo Problema Resolva a relacao de recorrˆencia an an1 3 para n 1 2 3 onde a0 2 Solucao Comecamos com a condicao inicial a0 2 e vamos aplicando sucessivamente a relacao de recorrˆencia ate que seja possıvel deduzir uma formula fechada para o termo geral an a1 a0 3 2 3 2 3 1 a2 a1 3 2 3 1 3 2 3 2 a3 a2 3 2 3 2 3 2 3 3 a4 a3 3 2 3 3 3 2 3 4 an an1 3 2 3 n 1 3 2 3n Portanto conjecturamos que an 2 3n e uma formula fechada para a recorrˆencia acima Temos que provar essa conjectura 30 Metodo da substituicao iterativo Problema Resolva a relacao de recorrˆencia an an1 3 para n 1 2 3 onde a0 2 Solucao Comecamos com a condicao inicial a0 2 e vamos aplicando sucessivamente a relacao de recorrˆencia ate que seja possıvel deduzir uma formula fechada para o termo geral an a1 a0 3 2 3 2 3 1 a2 a1 3 2 3 1 3 2 3 2 a3 a2 3 2 3 2 3 2 3 3 a4 a3 3 2 3 3 3 2 3 4 an an1 3 2 3 n 1 3 2 3n Portanto conjecturamos que an 2 3n e uma formula fechada para a recorrˆencia acima Temos que provar essa conjectura 30 Metodo da substituicao iterativo Problema Resolva a relacao de recorrˆencia an an1 3 para n 1 2 3 onde a0 2 Solucao Comecamos com a condicao inicial a0 2 e vamos aplicando sucessivamente a relacao de recorrˆencia ate que seja possıvel deduzir uma formula fechada para o termo geral an a1 a0 3 2 3 2 3 1 a2 a1 3 2 3 1 3 2 3 2 a3 a2 3 2 3 2 3 2 3 3 a4 a3 3 2 3 3 3 2 3 4 an an1 3 2 3 n 1 3 2 3n Portanto conjecturamos que an 2 3n e uma formula fechada para a recorrˆencia acima Temos que provar essa conjectura 30 Metodo da substituicao iterativo Problema Resolva a relacao de recorrˆencia an an1 3 para n 1 2 3 onde a0 2 Solucao Comecamos com a condicao inicial a0 2 e vamos aplicando sucessivamente a relacao de recorrˆencia ate que seja possıvel deduzir uma formula fechada para o termo geral an a1 a0 3 2 3 2 3 1 a2 a1 3 2 3 1 3 2 3 2 a3 a2 3 2 3 2 3 2 3 3 a4 a3 3 2 3 3 3 2 3 4 an an1 3 2 3 n 1 3 2 3n Portanto conjecturamos que an 2 3n e uma formula fechada para a recorrˆencia acima Temos que provar essa conjectura 30 Metodo da substituicao iterativo Continuacao da Solucao Vamos agora provar que an 2 3n e uma solucao para a relacao de recorrˆencia an an1 3 para n 1 2 3 onde a0 2 Vamos provar por inducao em n que an 2 3n Base Suponha n 0 Neste caso temos que a0 2 3 0 2 0 2 o que e verdade pela condicao inicial a0 2 Hipotese de Inducao Suponha que ak 2 3k seja verdade para um k arbitrario onde k 0 Passo Indutivo Provase a seguir que ak1 2 3k 1 Pela definicao da relacao de recorrˆencia para a sequˆencia an temos que ak1 ak 3 HI 2 3k 3 2 3k 1 Isso conclui o passo indutivo Portanto como a base e o passo indutivo foram provados concluımos que an 2 3n 31 Metodo da substituicao iterativo Continuacao da Solucao Vamos agora provar que an 2 3n e uma solucao para a relacao de recorrˆencia an an1 3 para n 1 2 3 onde a0 2 Vamos provar por inducao em n que an 2 3n Base Suponha n 0 Neste caso temos que a0 2 3 0 2 0 2 o que e verdade pela condicao inicial a0 2 Hipotese de Inducao Suponha que ak 2 3k seja verdade para um k arbitrario onde k 0 Passo Indutivo Provase a seguir que ak1 2 3k 1 Pela definicao da relacao de recorrˆencia para a sequˆencia an temos que ak1 ak 3 HI 2 3k 3 2 3k 1 Isso conclui o passo indutivo Portanto como a base e o passo indutivo foram provados concluımos que an 2 3n 31 Metodo da substituicao iterativo Continuacao da Solucao Vamos agora provar que an 2 3n e uma solucao para a relacao de recorrˆencia an an1 3 para n 1 2 3 onde a0 2 Vamos provar por inducao em n que an 2 3n Base Suponha n 0 Neste caso temos que a0 2 3 0 2 0 2 o que e verdade pela condicao inicial a0 2 Hipotese de Inducao Suponha que ak 2 3k seja verdade para um k arbitrario onde k 0 Passo Indutivo Provase a seguir que ak1 2 3k 1 Pela definicao da relacao de recorrˆencia para a sequˆencia an temos que ak1 ak 3 HI 2 3k 3 2 3k 1 Isso conclui o passo indutivo Portanto como a base e o passo indutivo foram provados concluımos que an 2 3n 31 Metodo da substituicao iterativo Continuacao da Solucao Vamos agora provar que an 2 3n e uma solucao para a relacao de recorrˆencia an an1 3 para n 1 2 3 onde a0 2 Vamos provar por inducao em n que an 2 3n Base Suponha n 0 Neste caso temos que a0 2 3 0 2 0 2 o que e verdade pela condicao inicial a0 2 Hipotese de Inducao Suponha que ak 2 3k seja verdade para um k arbitrario onde k 0 Passo Indutivo Provase a seguir que ak1 2 3k 1 Pela definicao da relacao de recorrˆencia para a sequˆencia an temos que ak1 ak 3 HI 2 3k 3 2 3k 1 Isso conclui o passo indutivo Portanto como a base e o passo indutivo foram provados concluımos que an 2 3n 31 Metodo da substituicao iterativo Continuacao da Solucao Vamos agora provar que an 2 3n e uma solucao para a relacao de recorrˆencia an an1 3 para n 1 2 3 onde a0 2 Vamos provar por inducao em n que an 2 3n Base Suponha n 0 Neste caso temos que a0 2 3 0 2 0 2 o que e verdade pela condicao inicial a0 2 Hipotese de Inducao Suponha que ak 2 3k seja verdade para um k arbitrario onde k 0 Passo Indutivo Provase a seguir que ak1 2 3k 1 Pela definicao da relacao de recorrˆencia para a sequˆencia an temos que ak1 ak 3 HI 2 3k 3 2 3k 1 Isso conclui o passo indutivo Portanto como a base e o passo indutivo foram provados concluımos que an 2 3n 31 Metodo da substituicao iterativo Continuacao da Solucao Vamos agora provar que an 2 3n e uma solucao para a relacao de recorrˆencia an an1 3 para n 1 2 3 onde a0 2 Vamos provar por inducao em n que an 2 3n Base Suponha n 0 Neste caso temos que a0 2 3 0 2 0 2 o que e verdade pela condicao inicial a0 2 Hipotese de Inducao Suponha que ak 2 3k seja verdade para um k arbitrario onde k 0 Passo Indutivo Provase a seguir que ak1 2 3k 1 Pela definicao da relacao de recorrˆencia para a sequˆencia an temos que ak1 ak 3 HI 2 3k 3 2 3k 1 Isso conclui o passo indutivo Portanto como a base e o passo indutivo foram provados concluımos que an 2 3n 31 Metodo da substituicao iterativo Continuacao da Solucao Vamos agora provar que an 2 3n e uma solucao para a relacao de recorrˆencia an an1 3 para n 1 2 3 onde a0 2 Vamos provar por inducao em n que an 2 3n Base Suponha n 0 Neste caso temos que a0 2 3 0 2 0 2 o que e verdade pela condicao inicial a0 2 Hipotese de Inducao Suponha que ak 2 3k seja verdade para um k arbitrario onde k 0 Passo Indutivo Provase a seguir que ak1 2 3k 1 Pela definicao da relacao de recorrˆencia para a sequˆencia an temos que ak1 ak 3 HI 2 3k 3 2 3k 1 Isso conclui o passo indutivo Portanto como a base e o passo indutivo foram provados concluımos que an 2 3n 31 Metodo da substituicao iterativo Continuacao da Solucao Vamos agora provar que an 2 3n e uma solucao para a relacao de recorrˆencia an an1 3 para n 1 2 3 onde a0 2 Vamos provar por inducao em n que an 2 3n Base Suponha n 0 Neste caso temos que a0 2 3 0 2 0 2 o que e verdade pela condicao inicial a0 2 Hipotese de Inducao Suponha que ak 2 3k seja verdade para um k arbitrario onde k 0 Passo Indutivo Provase a seguir que ak1 2 3k 1 Pela definicao da relacao de recorrˆencia para a sequˆencia an temos que ak1 ak 3 HI 2 3k 3 2 3k 1 Isso conclui o passo indutivo Portanto como a base e o passo indutivo foram provados concluımos que an 2 3n 31 Resolvendo Relacoes de Recorrˆencia Exercıcio para Casa Resolva a relacao de recorrˆencia an 2 an1 para n 2 3 4 onde a1 2 32 Somatórios Somatorios Intuitivamente sao somas dos termos de alguma sequˆencia an A estrutura das sequˆencias domınio nos inteiros favorece a resolucao de somas longas dos seus termos em menos passos Nosso objetivo e utilizar as propriedades de somatorios para simplificar somas longas 34 Somatórios Notação A soma dos termos am am1 an pode ser expressa como jmn aj jmn aj ou mjn aj 35 Somatórios Notação A soma dos termos am am1 an pode ser expressa como jmn aj jmn aj ou mjn aj Cada notação envolve quatro elementos j m n aj j é a variável de índice a escolha da variável j como índice é arbitrária 35 Somatórios Notação A soma dos termos am am1 an pode ser expressa como jmn aj jmn aj ou mjn aj Cada notação envolve quatro elementos j m n aj j é a variável de índice a escolha da variável j como índice é arbitrária m é o valor inicial limite inferior que j assume Somatórios Notação A soma dos termos am am1 an pode ser expressa como jmn aj jmn aj ou mjn aj Cada notação envolve quatro elementos j m n aj j é a variável de índice a escolha da variável j como índice é arbitrária m é o valor inicial limite inferior que j assume n é o valor final limite superior que j assume Somatórios Notação A soma dos termos am am1 an pode ser expressa como jmn aj jmn aj ou mjn aj Cada notação envolve quatro elementos j m n aj j é a variável de índice a escolha da variável j como índice é arbitrária m é o valor inicial limite inferior que j assume n é o valor final limite superior que j assume aj é a sequência utilizada Somatórios Exemplo 1 A expressão j1 a 10 aj codifica a soma dos termos de aj indo de a1 até a10 Ou seja j1 a 10 aj a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 Somatórios Exemplo 1 A expressão j1 a 10 aj codifica a soma dos termos de aj indo de a1 até a10 Ou seja j1 a 10 aj a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 Se fizermos aj 2j então a expressão j1 a 10 aj codifica j1 a 10 aj a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 21 22 23 24 25 26 27 28 29 210 2 4 6 8 10 12 14 16 18 20 110 Somatórios Exemplo 2 Exemplo O que significa j1 a 100 1j Somatórios Exemplo 2 Exemplo O que significa É a soma dos termos a1 a2 a3 a100 da sequência aj com aj 1j Somatórios Exemplo 2 Exemplo O que significa É a soma dos termos a1 a2 a3 a100 da sequência aj com aj 1j Constatação Teremos 11 12 13 1100 Somatórios Exemplo 3 Exemplo O que significa Somatórios Exemplo 3 Exemplo O que significa k48 1k É a soma dos termos a4 a5 a8 da sequência ak com ak 1k Constatação Teremos 14 15 16 17 18 1 1 1 1 1 1 Propriedades do Somatório Propriedades do Somatorio Nosso objetivo Somar numeros de uma sequˆencia dois a dois e ineficiente Podemos economizar trabalho e tempo usando propriedades das operacoes aritmeticas adaptadas aos somatorios Da aritmetica para x y z numeros quaisquer temos Comutatividade x y y x Associatividade x y z x y z Distributividade xy z xy xz 40 Propriedades do Somatório Em somatórios temos Comutatividade jmn aj bj jmn aj jmn bj Associatividade jmn aj jmn aj jl1n aj Distributividade jmn k aj k jmn aj Comutatividade Vamos analisar a igualdade Comutatividade aj bj aj bj n jm n jm n jm Comutatividade Vamos analisar a igualdade Comutatividade aj bj aj bj n jm n jm n jm Começando do lado esquerdo temos aj bj am bm am1 bm1 an bn n jm am am1 an bm bm1 bn aj bj n jm n jm Associatividade Vamos analisar a igualdade Associatividade aj aj aj n jm jm jℓ1 Associatividade Vamos analisar a igualdade Associatividade jmn aj jmℓ aj jℓ1n aj Começando do lado esquerdo temos jmn aj am am1 an am am1 aℓ aℓ1 an am am1 aℓ aℓ1 an jmℓ aj jℓ1n aj Distributividade Vamos analisar a igualdade Distributividade jmn k aj k jmn aj Distributividade Vamos analisar a igualdade Distributividade jmn k aj k jmn aj Começando do lado esquerdo temos jmn k aj kam kam1 kan k am am1 an k jmn aj Como resolver somatórios Como resolver Somatórios Ao encontrar somatórios complicados nosso primeiro interesse é simplificar essas expressões Exemplo 1 Considere que desejamos calcular j1 10 2j Como resolver Somatórios Ao encontrar somatórios complicados nosso primeiro interesse é simplificar essas expressões Exemplo 1 Considere que desejamos calcular j1 10 2j Pela distributividade podemos simplificar a expressão para obter j1 10 2j 2 j1 10 j Como resolver Somatórios Ao encontrar somatórios complicados nosso primeiro interesse é simplificar essas expressões Exemplo 1 Considere que desejamos calcular j110 2j Pela distributividade podemos simplificar a expressão para obter j110 2j 2 j110 j Observação Note que houve uma troca Ao invés de calcularmos j110 2j basta calcular j110 j para multiplicar o resultado por dois Como resolver Somatórios Exemplo 2 Considere que desejamos calcular j110 2j 3 Como resolver Somatórios Exemplo 2 Considere que desejamos calcular j110 2j 3 Pela comutatividade podemos simplificar a expressão para obter j110 2j 3 2 j110 j j110 3 Como resolver Somatórios Nosso segundo interesse é encontrar somas conhecidas no processo Por exemplo é muito útil saber que para todo n N j1n j nn12 Como resolver Somatórios Nosso segundo interesse é encontrar somas conhecidas no processo Por exemplo é muito útil saber que para todo n N j1n j nn12 Como resolver Somatórios Exemplo 2 Considere que desejamos calcular j110 2j3 Pela comutatividade podemos simplificar a expressão para obter j110 2j3 2j110 j j110 3 Observação Houve uma troca Ao invés de calcularmos j110 2j3j basta calcular j110 2j e j110 3 para então somálas Note que j110 2j é a expressão do exemplo anterior Como resolver Somatórios Nosso segundo interesse é encontrar somas conhecidas no processo Por exemplo é muito útil saber que para todo n N j1n j nn12 Exemplo 1 Continuação Pela fórmula j110 j 101012 1102 55 Agora podemos completar o primeiro exemplo obtendo j110 2j 2 j110 j 2 55 110 Como resolver Somatórios Também é muito útil saber que para todo n N j1n 1 n Como resolver Somatórios Também é muito útil saber que para todo n N j1n 1 n Exemplo 2 Continuação Temos j110 2j 3 j110 2j 3 j110 2j j110 3 2 j110 j 3 j110 1 2 101012 3 10 2 55 30 140 Algumas somas importantes Exercício Usando indução matemática prove as seguintes fórmulas Soma Fórmula Fechada Σk0n a rk r 1 a rn1ar1 r 1 Σk1n k nn12 Σk1n k2 nn12n16 Σk1n k3 n2 n124 Σk0n k dj 2kdnn12 Tabela Algumas somas importantes Algumas somas importantes A partir destas somas conhecidas podemos resolver muitos problemas Podemos também generalizar estas somas usando associatividade Exemplo Considere que desejamos calcular Σi3060 i Algumas somas importantes A partir destas somas conhecidas podemos resolver muitos problemas Podemos também generalizar estas somas usando associatividade Exemplo Considere que desejamos calcular Σi3060 i Observe que Σi3060 i Σi160 i Σi129 i e utilize a fórmula geral Σj1n j nn12 para calcular os termos da subtração Algumas somas importantes A partir destas somas conhecidas podemos resolver muitos problemas Podemos também generalizar estas somas usando associatividade Exemplo Considere que desejamos calcular sum i3060 i Observe que sum i3060 i sum i160 i sum i129 i e utilize a fórmula geral sum j1n j nn12 para calcular os termos da subtração Temos sum i160 i 606012 30 61 1830 e sum i129 i 2929 12 29 15 435 Algumas somas importantes A partir destas somas conhecidas podemos resolver muitos problemas Podemos também generalizar estas somas usando associatividade Exemplo Considere que desejamos calcular sum i3060 i Observe que sum i3060 i sum i160 i sum i129 i e utilize a fórmula geral sum j1n j nn12 para calcular os termos da subtração Daí sum i3060 i sum i160 i sum i129 i 1830 435 1395 Algumas somas importantes A partir destas somas conhecidas podemos resolver muitos problemas Podemos também generalizar estas somas usando associatividade No caso geral para sum iml i Algumas somas importantes A partir destas somas conhecidas podemos resolver muitos problemas Podemos também generalizar estas somas usando associatividade No caso geral para iml i Observe que iml i i1l i i1m1 i e utilize a fórmula geral j1n j nn12 para calcular os termos da subtração Algumas somas importantes A partir destas somas conhecidas podemos resolver muitos problemas Podemos também generalizar estas somas usando associatividade No caso geral para iml i Observe que iml i i1l i i1m1 i e utilize a fórmula geral j1n j nn12 para calcular os termos da subtração Temos i1l i ll12 e i1m1 i m1m112 mm12 Algumas somas importantes A partir destas somas conhecidas podemos resolver muitos problemas Podemos também generalizar estas somas usando associatividade No caso geral para iml i Observe que iml i i1l i i1m1 i e utilize a fórmula geral j1n j nn12 para calcular os termos da subtração Temos i1l i ll12 e i1m1 i m1m112 mm12 Daí iml i i1l i i1m1 i ll12 mm12 mllm12 Mudanças de Índice Mudanças de Índice Às vezes pode ser importante mudarmos o índice de um somatório Mudanças de Índice Às vezes pode ser importante mudarmos o índice de um somatório Exemplo Considere a soma j 1 k j1 k3