Teoria_morgado_binomiodenewton

Departamento de Estatística e Matemática Aplicada DEMA Universidade Federal do Ceará Semestre 2020.1 CC0279 - Elementos de Análise Combinatória Teoria do Cap 4- Seções 4.2 e 4.3 do Morgado - 20/07/2020 Prof. Mauricio Mota 1. ( Teorema -pg 104) Se x e a são números reais e n é um inteiro positivo (x + a)^n = \sum_{k=0}^{n} \binom{n}{k} a^k x^{n-k}. Note que: (x + a)^n = (x + a)(x + a) \cdots (x + a) = P_1P_2 \cdots P_n. Quantas vezes aparece a^k x^{n-k}? Para isto devemos escolher um a de k produtos entre os produtos P_1P_2 \cdots P_n dos restantes (n - k) a gente escolhe o fator x. Assim há \binom{n}{k} de escolher os k produtos. A expansão geral é a soma destes termos. vamos expandir o somatório: (x + a)^n = \binom{n}{0} x^n + \binom{n}{1} a^1x^{n-1} + \binom{n}{2} a^2 x^{n-2} + \cdots + \binom{n}{n} a^n. Na realidade temos um polinômio de grau n na variável x: P(x) = (x + a)^n = A_0 + A_1x + A_2x^2 + \cdots + A_nx^n, em que A_k = \binom{n}{k} a^k, k = 0, 1, 2, \ldots, n. Note que: P(1) = A_0 + A_1 + A_2 + \cdots + A_n = \sum_{k=0}^{n} A_k, isto é, a soma dos coeficientes do desenvolvimento P(x) = (x + a)^n é o valor numérico do polinômio calculado no ponto x = 1, isto é, S = P(1) = (1 + a)^n = \sum_{k=0}^{n} \binom{n}{k} a^k. i. O desenvolvimento de (x + a)^n possui (n+1) termos. ii. Os coeficientes do desenvolvimento de (x + a)^n são os elementos da linha n do triângulo de Pascal. Note que: A linha 0 é dada por: (x + a)^0 = 1 = \binom{0}{0} x^0 Departamento de Estatística e Matemática Aplicada DEMA Universidade Federal do Ceará Semestre 2020.1 A linha 1 é dada por: (x + a)^1 = x + a = \binom{1}{0} x + \binom{1}{1} a A linha 2 é dada por: (x + a)^2 = x^2 + 2ax + a^2 = \binom{2}{0} x^2 + \binom{2}{1} ax + \binom{2}{2} a^2 A linha 3 é dada por: (x + a)^3 = x^3 + 3ax^2 + 3a^2x + a^3 = \binom{3}{0} x^3 + \binom{3}{1} ax^2 + \binom{3}{2} a^2x + \binom{3}{3} a^3 A linha 4 é dada por: (x + a)^4 = x^4 + 4ax^3 + 6a^2x^2 + 3a^3x + a^4 = \binom{4}{0} x^4 + \binom{4}{1} ax^3 + \binom{4}{2} a^2x^2 + \binom{4}{3} a^3x + \binom{4}{4} a^4, e assim por diante. iii. Escrevendo os termos do desenvolvimento na ordem decrescente das potências de x, o termo de ordem (k + 1) é dado por: T_{k+1} = \binom{n}{k} a^k x^{n-k}, k = 0, 1, 2, \ldots, n. Geralmente o binômio de Newton pode aparecer como: (a + b)^n = \sum_{k=0}^{n} \binom{n}{k} b^k a^{n-k}. As vezes aparece na forma: P(x) = (a(x) + b(x))^n = \sum_{k=0}^{n} \binom{n}{k} [b(x)]^k [a(x)]^{n-k}. Neste caso a soma dos coeficientes de é dada por: \left(\right)^n. Outras vezes aparece como: (a - b)^n = (a + (- Vamos resolver alguns exemplos: Exemplo 1. Det ermine o coeficiente de no desenvolvimento de e Solução: Departamento de Estatística e Matemática Aplicada DEMA Universidade Federal do Ceará Semestre 2020.1 Vemos que n = 9 e a(x) = x^3 e b(x) = \frac{1}{x^2} = -x^{-2}. O termo genérico do desenvolvimento é dado por: T_{k+1} = \binom{n}{k} a^k x^{n-k} = \binom{n}{k} (-x^{-2})^k (x^3)^{9-k} = \binom{n}{k} (-1)^k x^{-2k} x^{27-3k} = \binom{n}{k} (-1)^k x^{27-5k}. O problema pede o termo em x^2, logo 27 - 5k = 2, o que acarreta k = 5. Assim k + 1 = 6. O termo de posição 6 é dado por: T_6 = \binom{9}{5} (-1)^5 x^{27-25} = -126x^2, e o coeficiente vale -126. Exemplo 2. Determine o termo máximo do desenvolvimento de \left(1 + \frac{1}{3}\right)^{65}. Solução: Vemos que n = 65 e a = 1 e b = \frac{1}{3}. O termo genérico do desenvolvimento é dado por: T_{k+1} = \binom{65}{k} \left(\frac{1}{3}\right)^k 1^{65-k} = \binom{65}{k} \left(\frac{1}{3}\right)^k = \binom{65}{k} \frac{1}{3^k} = \frac{65!}{k!(65-k)!3^k}. Para que valores de k temos Departamento de Estatística e Matemática Aplicada Universidade Federal do Ceará DEMA Semestre 2020.1 T_{k+1} > T_k? Note que T_k = T_{k-1+1} = \dbinom{65}{k-1} \frac{1}{3^{k-1}} = \frac{65!}{k!(66-k)!}3^{k-1} . Vamos arrumar de modo conveniente e cancelando 65! \frac{(66-k)!}{(65-k)!} > \frac{k!}{(k-1)!} \frac{3^k}{3^{k-1}} Simplificando \frac{(66-k)(65-k)!}{(65-k)!} \frac{k!}{(k-1)!} \frac{3^k}{3^{k-1}} ou 66-k > 3k , e k < \frac{66}{4} = 16,5 . Logo T_{k+1} > T_k para k \in \{0,1,2,\ldots,16\} e analogamente T_{k+1} < T_k para k \in \{17,18,\ldots,65\}. Vamos juntar tudo: T_1 < T_2 < T_3 < \ldots < T_{16} > T_{17} > T_{18} > \ldots > T_{66} . Assim o termo máximo é T_{17} = \dbinom{65}{16}. Vamos ver a solução pelo > n=65 > > k=0:n;k [1] 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 [26] 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 [51] 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 > > ###a_k=T_{k+1} > a_k=choose(n,k)*(3^(-k)) > max(ak) [1] 15054479 > which.max(ak) ###assim k=16, e o máximo é T_17. [1] 17 > Exemplo 3. Determine o termo máximo do desenvolvimento de P(x) = (1+x)^9 = \sum_{k=0}^{9} \binom{9}{k} x^k . Solução: Assim T_{k+1} = \binom{9}{k}, k = 0,1,2,\ldots,10. Logo T_1 = T_{10} = \binom{9}{0} = \binom{9}{9} = 1, T_2 = T_9 = \binom{9}{1} = \binom{9}{8} = 9, T_3 = T_8 = \binom{9}{2} = \binom{9}{7} = 36, T_4 = T_7 = \binom{9}{3} = \binom{9}{6} = 84, T_5 = T_6 = \binom{9}{4} = \binom{9}{5} = 126. Usando o software R temos: > n=9 > k=0:n;k [1] 0 1 2 3 4 5 6 7 8 9 > T_k=choose(n,k);T_k [1] 1 9 36 84 126 126 84 36 9 1 > O valor máximo é 126. Os termos são T_5 e T_6. Perceba que neste caso são dois valores de k que atingem o valor máximo. Vamos formalizar? Quando há duas modas temos que procurar valores de k tais que: T_{k+1} = T_k? Sabemos que T_{k+1} = \binom{9}{k}, k = 0,1,2,\ldots,10, e T_{k-1+1} = \binom{9}{k-1}, k = 1,2,\ldots,10. Assim, T_{k+1} = T_k, \binom{9}{k} = \binom{9}{k-1}, Logo como k \ne k-1 e usando as propriedades de combinações complementares temos: k + k - 1 = 9, 2k = 10, k = 5. Logo T_5 = T_6. Quando T_{k+1} < T_k? \frac{9!}{k!(9-k)!} < \frac{9!}{(k-1)!(10-k)!}. simplificando 9! e manipulando os termos: \frac{(k-1)!}{k!} < \frac{(9-k)!}{(10-k)!} vamos brincar um pouco mais: \frac{(k-1)!}{k(k-1)!} < \frac{(9-k)!}{(10-k)(9-k)!} simplificando \frac{1}{k} < \frac{1}{(10-k)} logo 10-k < k, 10 < 2k, Departamento de Estatística e Matemática Aplicada Universidade Federal do Ceará DEMA Semestre 2020.1 e k > 5. Isto quer dizer: T_7 < T_6, T_8 < T_7, T_9 < T_8, T_10 < T_9, T_11 < T_10. Para k = 1, 2, 3, 4, 5 temos T_{k+1} > T_k Logo T_1 < T_2 < T_3 < T_4 < T_5. Juntando tudo temos: T_1 < T_2 < T_3 < T_4 < T_5 = T_6 > T_7 > T_8 > T_9 > T_10 > T_11. T_5 e T_6 são os termos com valores máximos. Esta técnica será empregada em Probabilidade I para calcular a moda das variáveis discretas como a Poisson, Pascal e a Binomial. > > n=9 > > k=0:n;k [1] 0 1 2 3 4 5 6 7 8 9 > C_k=choose(n,k);C_k [1] 1 9 36 84 126 126 84 36 9 1 > ##o valor máximo 126 ocorre nas posições 5 e 6. > > max(C_k) [1] 126 > > which.max(C_k) ####Cuidado ele fornece a posição da primeira posição. [1] 5 > > Exemplo 4. Qual é a soma dos coeficientes do desenvolvimento de P(x) = (x^3 - 2x^2)^{15}. Solução: O desenvolvimento do binômio tem 16 termos. Poderíamos calcular cada termo e depois somá-los. Esta técnica é muito trabalhosa. Vamos pensar em outra. Se tivermos um polinômio de grau m, isto é, Departamento de Estatística e Matemática Aplicada Universidade Federal do Ceará DEMA Semestre 2020.1 P(x) = \sum_{i=0}^{m} A_i x^i = A_0 + A_1 x + A_2 x^2 + \ldots + A_m x^m. O valor numérico de P(x) para x = 1 nos dará a soma pretendida. P(1) = \sum_{i=0}^{m} A_i 1^i = A_0 + A_1 + A_2 + \ldots + A_m = \sum_{i=0}^{m} A_i. Assim \sum_{i=0}^{m} A_i = P(1) = (1^3 - 2 \times 1^2)^{15} = (-1)^{15} = -1. Vamos fazer de outra maneira usando o software R: Note que o termo geral é dado por: T_k+1 = \binom{15}{k} (-2x^2)^k (x^3)^{15-k} = \binom{15}{k} (-2)^k x^{45-k}. Para k=0 temos o expoente m = 45 que é o grau do nosso polinômio. Logo \sum_{k=0}^{15} A_k = \sum_{k=0}^{15} \binom{15}{k} (-2)^k = \sum_{k=0}^{15} \binom{15}{k} (-2)^k 1^{15-k} = \sum_{k=0}^{15} \binom{15}{k} (-2)^k 1 15-k = (-2 + 1)^{15} = -1, note que 1^{15-k} = 1, belo truque não? multiplicar por 1 não altera. Seja T_k o k-ésimo coeficiente termo. assim, T_k = \binom{15}{k-1}(-2)^{k-1}. > n=15 > k=1:(n+1);k [1] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 > T_k=(-2)^{k-1}*choose(15,k-1);T_k [1] 1 -30 420 -3640 21840 -96096 320320 -823680 [9] 1647360 -2562560 3075072 -2795520 1863680 -860160 245760 -32768 > > sum(T_k) [1] -1 > Departamento de Estatística e Matemática Aplicada Universidade Federal do Ceará DEMA Semestre 2020.1 Os próximos exemplos são somatórios que precisam ser transformados em Binômio de Newton. Vamos aprender? Exemplo 5. Calcule \displaystyle S = \sum_{k=0}^{n} \binom{n}{k} x^k. Solução: Note que: S = \sum_{k=0}^{n} \binom{n}{k} x^k \times 1 = \sum_{k=0}^{n} \binom{n}{k} x^k \times 1^{n-k} = . Temos a fórmula do Binômio de Newton. Logo S = (1 + x)^{n} = (x + 1)^{n}. Exemplo 6. Calcule \displaystyle S = \sum_{k=0}^{n} \binom{n}{k} k x^k. Solução: Note que para k=0 o coeficiente é nulo e assim não altera a soma. Vamos começar o somatório com k = 1. S = \sum_{k=0}^{n} \binom{n}{k} x^k = \sum_{k=0}^{n} \binom{n}{k} k x^k. Vamos simplificar usando o fato que k não é zero.: k\binom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{n!}{(k-1)!(n-k)!} = \frac{(n-1)!}{(k-1)!(n-k)!}. = \binom{n-1}{k-1}. Logo, S = \sum_{k=1}^{n} \binom{n}{k} k x^k = \sum_{k=1}^{n} \binom{n-1}{k-1} x^k. Fazendo a mudança de variável i = k-1 no somatório temos que para k = 1 temos i = 1-1 = 0 e para k = n temos i = n-1. Note que k = i + 1. Departamento de Estatística e Matemática Aplicada Universidade Federal do Ceará DEMA Semestre 2020.1 Dessa maneira S = n ∑(n−1) (n−1) zk = n ∑ (n−1) xi+1 = nz ∑ (n−1) xi. k=1 (k−1) i=0 i i=0 i S = nz ∑ (n−1) xi = nz ∑ (n−1) xi x1n−1−i = nz(1+ x)n−1. i=0 i i=0 i Uma outra solução envolve derivada. Considere a função real de variável real f(x) = (1 + x)n, cuja derivada em relação a x é dada por: f '(x) = n(1+ x)n−1. Usando Binômio de Newton podemos pensar também: f(x) = (1 + x)n = ∑ n(k) zk, k=0 cuja derivada em relação a x é dada por: f '(x) = ∑ n(k) zk−1. k=0 Igualando as duas termos: ∑ n(k) zk−1 = n(1+ x)n−1, k=0 multiplicando ambos os lados por x temos ∑ n(k) zk = nx(1+ x)n−1. k=0 Exemplo 7. Usando o exemplo 6 mostre que: ∑ n(k) = n2n−1. k=0 Solução: Note que: f(1) = ∑ n(k) 1k = n ×1× ( k=0 Exemplo 7. Mostre que Departamento de Estatística e Matemática Aplicada Universidade Federal do Ceará DEMA Semestre 2020.1 ∑ n(k) = 2n. k=0 Solução: Vamos usar a fórmula do binômio de Newton: (x + a)n = ∑ n(k) akxn−k, k=0 fazendo a = x = 1 temos: (1 + 1)n = ∑ n(k) 1k1n−k = ∑ n(k) 1k = 2n. k=0 k=0 Exemplo 8. Mostre que ∑ (−1)k n(k) = 2n. k=0 Solução: Vamos usar a fórmula do binômio de Newton: (x + a)n = ∑ n(k) akxn−k, k=0 fazendo a = −1 e x = 1 temos: (1 − 1)n = ∑ n(k) (−1)kn−k = ∑ (−1)k n(k) = 0n = 0. k=0 k=0 Exemplo 9. O próximo exemplo tratará de obter a soma dos termos de ordem par de um Binômio de Newton (x + a)n ordenado segundo as potências decrescentes de x. Seja Sp esta soma e Cp a soma dos coeficientes dos termos de ordem par . Mostre que: Sp = (x+ a)n − (x− a)n, 2 Cp = (1+ a)n − (1− a)n. 2 Solução: Vamos expandir (x + a)n (x + a)n = T1 + T2 + T3 + T4 + . . . e (x − a)n = T1 − T2 + T3 − T4 Subtraindo as duas expressões temos: − a)n = 2 [T2 + T4 + . . .] Departamento de Estatística e Matemática Aplicada Universidade Federal do Ceará DEMA Semestre 2020.1 (x+a)n = ∑ n(k) ak xn−k = ∑ nj=1 Tj. n=sum (x−a)n = ∑ n(k) (−1)kak xn−k = n=sum Subtraindo temos: (x+ a)n − (x− a)n = n+sum − n=sum Vamos colocar o − do segundo somatório para o interior do mesmo. (x+ a)n − (x− a)n = ∑ n+sum Tj + ∑ (−1)j−1Tj. j=1 j=1 (x+ a)n − (x− a)n = ∑ n+sum ((1+ (−1)j)Tj j=1 (x+ a)n − (x− a)n = ∑ n+sum (1+(−1). j=1 mas se j é ímpar se j é par . Assim, para todos os valores de tais que . Assim, Para calcular a soma dos coeficientes de ordem par basta fazer . + a)n − (1− a)n, 2 Departamento de Estatística e Matemática Aplicada Universidade Federal do Ceará DEMA Semestre 2020.1 Vamos considerar um exemplo para ilustrar: Considere (x + 2)^4 = x^4 + 8x^3 + 24x^2 + 32x + 16 = T_1x^4 + T_2x^3 + T_3x^2 + T_4x + T_5 e Considere (x - 2)^4 = x^4 - 8x^3 + 24x^2 - 32x + 16 = T_1x^4 - T_2x^3 + T_3x^2 - T_4x + T_5 Assim, S_p = T_2 + T_4 = 16x^3 + 64x = 2[T_2 + T_4]. Se vc quiser saber a soma dos coeficientes de ordem par 8 + 32 = 40 é só fazer: C_p = P(1) = \frac{(1 + a)^n - (1 - a)^n}{2} = \frac{(1 + 2)^4 - (1 - 2)^4}{2} = \frac{3^4 - (-1)^4}{2} = \frac{81 - 1}{2} = 40. 2. Polinômio de Leibniz. Vamos generalizar a fórmula do binômio de Newton. O que seria por exemplo (a + b + c)^2? (a + b + c)^2 = (a + b + c)(a + b + c) = a^2 + b^2 + c^2 + 2ab + 2ac + 2bc. O que seria por exemplo (a + b + c)^3? (a + b + c)^3 = (a + b + c)(a + b + c)^2 = a^3 + b^3 + c^3 + 3a^2b + 3a^2c + 3b^2c + 3ab^2 + 3ac^2 + 3bc^2 + Temos 10 termos. Como explicar isso a priori? Note que cada termo é da forma abc com não negativos. Se a tem . Se b tem . Se c tem . Se k = 1 tem abc. Logo teremos tantos termos quantas são as soluções não negativas da equação: i + j + Sabemos que ( Morgado páginas 48 a 52 ) que o número de soluções inteiras não negativas da equação é dada por No nosso caso temos e . Logo (3 - 1) = ( 3 - 1) Departamento de Estatística e Matemática Aplicada Universidade Federal do Ceará DEMA Semestre 2020.1 O termo geral de (a + b + c)^3 é dado por: TG = \frac{3!}{i!j!k!} a^i b^j c^k, i + j + k = 3. O termo geral de (a + b + c)^n é dado por: TG = \frac{n!}{i!j!k!} a^i b^j c^k, i + j + k = n. Vamos enunciar a generalização do teorema. (x_1 + x_2 + ... + x_p)^n = \sum \frac{n!}{a_1!a_2!...a_p!} x_1^{a_1} x_2^{a_2}...x_p^{a_p}. O somatório é feito para todos os valores inteiros não negativos de a_1, a_2,..., a_p tais que a_1 + a_2 + ... + a_p = n. Exemplo 10. Considere a expressão (x^2 + 2x - 1)^4 . Responda: a. Quantos termos há na expressão? Solução: Fazendo a1 = x^2, x2 = 2x e x3 = -1 temos k = 3 e n = 4. O número de termos é dado CR^3_4 = \frac{3 + 4 - 1}{4} = \binom{6}{4} = 15 termos. b. Qual a expressão do termo Geral? Solução: TG = \frac{4!}{a_1!a_2!a_3!} x_1^{a_1} x_2^{a_2} x_3^{a_3}, a_1 + a_2 + a_3 = 4. TG = \frac{4!}{a_1!a_2!a_3!} (2x)^{a_2}(-1)^{a_3} = (-1)^{a_3}2^{a_2}\binom{4}{a_3}x^a_2, com a_1 = a_2 = a_3 + c. Existe algum termo da expressão que independe de x ? Solução: Assim o coeficiente de x neste termo deve valer zero. logo a_2 + a_3 = 4. Logo, a_1 = 0, Seu coeficiente é dado por: C = \frac{4!}{0!0!} d. Determine o coeficiente de x Solução: Assim o coeficiente de x neste termo deve valer zero. logo a_1 + a_3 = 4. As possíveis soluções são: Departamento de Estatística e Matemática Aplicada Universidade Federal do Ceará DEMA Semestre 2020.1 a_1 a_2 a_3 Termo 0 4 0 16x^4 1 2 1 -48x^4 2 0 0 6x^4 Somando temos que o termo em x^4 do desenvolvimento é -26x^4. O coeficiente vale -26. e. Determine a soma dos coeficientes desse desenvolvimento. Solução: A maior potência é x^8. Assim P(x) = (x^2 + 2x - 1)^4 = A_0 + A_1x + A_2x^2 + A_3x^3 + A_4x^4 + A_5x^5 + A_6x^6 + A_7x^7 + A_8x^8. Assim, P(1) = (1^2 + 2 \times 1 - 1)^4 = A_0 + A_1 + A_2 + A_3 + A_4 + A_5 + A_6 + A_7 + A_8 = 16. f. Mostre que P(x) = (x^2 + 2x - 1)^4 = 1 - 8x + 20x^2 - 8x^3 - 26x^4 + 8x^5 + 20x^6 + 8x^7 + x^8. Note que depois da redução dos termos semelhantes temos 9 termos. Solução: Ordem a_1 a_2 a_3 Termo 1 4 0 0 x^8 2 0 4 0 16x^4 3 0 0 4 1 4 3 1 0 8x^7 5 3 0 1 -4x^6 6 1 0 3 -4x^4 7 1 3 0 32x^5 8 0 1 3 -8x 9 0 3 1 -32x^3 10 2 1 1 -24x^5 11 1 2 1 -48x^4 12 1 2 2 24x^3 13 2 2 0 24x^6 14 2 0 0 6x^4 15 0 2 2 24x^2 Da última coluna ta tabela anterior obtemos: P(x) = (x^2 + 2x - 1)^4 = x \times 20x^6 + 8x^5 - 8 \times 4 - 8,x^2 - 1.