Questão 3

IME 2012

Matemática

[IME- 2012/2013 - 2ª fase]

Considere a matriz $A = egin{bmatrix} 2 &1 \ 0 & 2 end{bmatrix}$ . Seja a matriz $B = sum_{k=1}^{n}A^k$ , com $k$ e $n$ números inteiros. Determine a soma, em função de $n$ , dos quatro elementos da matriz $B$ .

Gabarito:

Resolução:

Primeiramente vamos desenvolver $A^k$ :

k = 1:

$A=egin{bmatrix} 2 &1 \ 0 & 2 end{bmatrix}$ .

k = 2:

$A^2=Acdot A=egin{bmatrix} 2 &1 \ 0 & 2 end{bmatrix}cdot egin{bmatrix} 2 &1 \ 0 & 2 end{bmatrix}=egin{bmatrix} 4 &4 \ 0 & 4 end{bmatrix}$ .

k = 3:

$A^3=A^2cdot A=egin{bmatrix} 4 &4 \ 0 & 4 end{bmatrix}cdot egin{bmatrix} 2 &1 \ 0 & 2 end{bmatrix}=egin{bmatrix} 8 &12 \ 0 & 8 end{bmatrix}$

k = 4:

$A^4=A^3cdot A=egin{bmatrix} 8 &12 \ 0 & 8 end{bmatrix}cdot egin{bmatrix} 2 &1 \ 0 & 2 end{bmatrix}=egin{bmatrix} 16 &32 \ 0 & 16 end{bmatrix}$

Nos parece que temos um padrão. O elemento abaixo da diagonal principal é sempre 0. Os elementos da diagonal principal parecem ser sempre iguais a $2^k$ e o elemento acima da diagonal principal parece ser proporcional a um exponencial de 2. A ideia é achar primeiramente qual o padrão verdadeiro para o elemento acima da diagonal principal e depois provarmos por indução que os elementos destas matrizes obedecerão sempre a este padrão.

Nós poderíamos ir chutando valores para o elemento acima da diagonal sabendo que ele seria algo parecido com um expoente de 2 e acharmos que o valor seria $2^{k-1}cdot k$ , porém, vou desenvolver um raciocínio que pode ser replicado em matrizes diferentes, mas que não será tão útil em alguns casos.

Repare que para acharmos o dito elemento nós sempre precisamos multiplicar o primeiro elemento da diagonal principal da matriz anterior, $A^{k-1}$ , por 1 (da matriz A) e somar o resultado disto com a multiplicação do elemento acima da diagonal principal da matriz anterior, $A^{k-1}$ , por 2 (da matriz A). Então teríamos como elemento acima da diagonal principal de $A^{k}$ :

$a_k=2^{k-1}cdot1+a_{k-1}cdot2=2^{k-1}+2a_{k-1}$ , onde $a_k$ é o elemento acima da diagonal principal da matriz $A^{k}$ . Veja que isto nos transmite a ideia de recorrência. Neste tipo de situação sempre nos lembremos da Soma Telescópica:

$a_k=2^{k-1}+2a_{k-1}$

+ $a_{k-1}=2^{k-2}+2a_{k-2}$

+ $a_{k-2}=2^{k-3}+2a_{k-3}$

+ $a_{k-3}=2^{k-4}+2a_{k-4}$

+ ...

+ $a_{k-left(k-3 ight )}=a_3=2^{k-left(k-2 ight )}+2a_{k-left(k-2 ight )}=2^2+2a_2$

+ $a_2=2^1+2a_1=2+2a_1$ , sendo $a_1=1$ .

Bom, esta soma não está legal pois termos da direita e esquerda em equações consecutivas não se cancelam. Mas repare que se multiplicarmos cada equação por $2^{m}$ , onde $m$ é o número que o $k$ subtrai no índice do $a$ no lado esquerdo de cada equação. Por exemplo, em $a_{k-2}=2^{k-3}+2a_{k-3}$ , $m$ seria igual a 2, daí, como resultado da multiplicação teríamos $2^2cdot a_{k-2}=2^2cdot 2^{k-3}+2^{2}cdot2a_{k-3}Rightarrow 4cdot a_{k-2}=2^{k-1}+8a_{k-3}$ .

Fazendo isto para todas as equações, teremos:

$a_k=2^{k-1}+2a_{k-1}$

+ $2a_{k-1}=2^{k-1}+4a_{k-2}$

+ $4a_{k-2}=2^{k-1}+8a_{k-3}$

+ $8a_{k-3}=2^{k-1}+16a_{k-4}$

+ ...

+ $2^{k-3}cdot a_{k-left(k-3 ight )}=2^{k-3}a_3=2^{k-1}+2^{k-2}cdot a_2$

+ $2^{k-2}a_2=2^{k-1}+2^{k-1}a_1$

Agora temos uma verdadeira soma telescópica. Cancelando os termos a serem cancelados, obtemos:

$a_k=left(2^{k-1}+2^{k-1}+...+2^{k-1} ight )+a_1cdot2^{k-1}$ , onde o número de elementos $2^{k-1}$ na soma é o número de equações na soma. É fácil ver que são $k-1$ equações, logo, $a_k=left(k-1 ight )cdot2^{k-1}+1cdot2^{k-1}=2^{k-1}cdot k$ .

Como achamos o elemento da diagonal principal, devemos provar por indução que

$A^k=egin{bmatrix} 2^k &kcdot 2^{k-1} \ 0& 2^k end{bmatrix}$

Para k + 1:

$A^{k+1}=A^k cdot A=egin{bmatrix} 2^k &kcdot 2^{k-1} \ 0& 2^k end{bmatrix}cdot egin{bmatrix} 2 &1 \ 0 & 2 end{bmatrix}= egin{bmatrix} 2^{k+1} &2^kcdot1+kcdot2^{k-1}cdot2 \ 0 & 2^{k+1} end{bmatrix}Rightarrow\\ Rightarrow A^{k+1}=egin{bmatrix} 2^{k+1} &kcdot2^{k} \ 0 & 2^{k+1} end{bmatrix}$

A matriz acima está de acordo com a regra geral. Se é válido para um natural posterior sempre, em todas as condições, então, indutivamente, deve ser válido para todo $k$ natural.

Logo, temos que $A^k=egin{bmatrix} 2^k &kcdot 2^{k-1} \ 0& 2^k end{bmatrix}$ .

Agora precisamos fazer a soma $B = sum_{k=1}^{n}A^k$ :

$B = egin{bmatrix} 2 &1 \ 0& 2 end{bmatrix}+egin{bmatrix} 4 &4 \ 0& 4 end{bmatrix}+...+egin{bmatrix} 2^n &ncdot2^{n-1} \ 0& 2^{n} end{bmatrix}Rightarrow\\ Rightarrow B = egin{bmatrix} 2+4+...+2^n &1+4+...+ ncdot2^{n-1}\ 0+0+...+0& 2+4+...+2^n end{bmatrix}$

Nos elementos da diagonal principal é nítido que temos uma soma de PG com elemento inicial 2, razão 2 e n elementos. O elemento acima da diagonal principal é uma soma da sequência com termo geral $kcdot 2^{k-1}$ .

A soma dos elementos da diagonal principal é dada por:

$2cdot S = 2cdotleft(2cdotleft(frac{2^{n}-1}{2-1} ight ) ight )=4cdotleft(2^n-1 ight )$

Agora vamos calcular a soma:

$S=1+4+12+32+...+ncdot2^{n-1}=sum_{k=1}^nkcdot2^{k-1}$

$2S=2 cdot 1+2cdot 4+2cdot 12+cdot 32+...+2cdot ncdot2^{n-1}=sum_{k=1}^nkcdot2^{k}$

subtraindo as duas temos:

$egin{matrix} 2S-S=&;sum_{k=1}^nkcdot2^{k}-sum_{k=1}^nkcdot2^{k-1}\ \ =&;left( sum_{k=1}^{n-1}kcdot2^{k} +ncdot 2^n ight )-left( 1cdot 2^{1-1}+sum_{k=2}^{n}kcdot2^{k-1} ight ) end{matrix}$

no segundo somatório ao invés de fazer k=2 até k=n trocamos por k=1 até k=n-1 portanto no lugar de k colocamos k+1:

$egin{matrix} 2S-S=&;left( sum_{k=1}^{n-1}kcdot2^{k} +ncdot 2^n ight )-left( 1cdot 2^{1-1}+sum_{k=1}^{n-1}(k+1)cdot2^{k} ight ) \ \ =&;ncdot 2^n-1+sum_{k=1}^{n-1}left[k-(k+1) ight]2^{k} \\ S=&;ncdot 2^n-1-sum_{k=1}^{n-1}2^{k}\\ =&;ncdot 2^n-1-2cdot frac{2^{n-1}-1}{2-1}\ =&;ncdot 2^n-2^n+1 end{matrix}$

Logo, a soma dos elementos de B é:

$S_B=4left(2^n-1 ight )+ncdot2^n-2^n+1=ncdot2^n+4cdot2^n-2^n+1-4Rightarrow\\ S_B=2^ncdotleft(n+3 ight )-3$ .

RESPOSTA: (n + 3) . 2ⁿ - 3.

Questão 3

IME 2012

Questões relacionadas

Questão 2

Questão 3

Questão 4

Questão 5