Teste 1 
Matemática Discreta LEIC 2007/2008

50 minutos
Enunciado A
Não é permitido o uso de máquinas de calcular nem de qualquer  tipo de consulta. 

Número:                                                       Nome:

Grupo I (1.5 val)

Mostre por indução que, para qualquer inteiro positivo n, (∑_(k=1)^n)k (2^k)=2+(n-1)(2^(n+1)).

Base de indução (n=1)

	(∑_(k=1)^1)k (2^k)=1 . (2^1)=2=2+0=2+0 . (2^2)=2+(1-1) (2^(1+1))

Passo de indução
	Hipótese de indução (HI):(∑_(k=1)^n)k (2^k)=2+(n-1) (2^(n+1))

Tese:(∑_(k=1)^(n+1))k (2^k)=2+n (2^(n+2))

(∑_(k=1)^(n+1))k (2^k)=((∑_(k=1)^n)k (2^k))+(n+1)(2^(n+1))(Subscript[=, HI])2+(n-1) (2^(n+1))+(n+1)(2^(n+1))=2+(n-1+n+1)(2^(n+1))=2+2n (2^(n+1))=2+n (2^(n+2))

Grupo II (2.0 val)

Usando o resultado do Grupo I, calcule justificadamente o somatório (∑_(i=1)^n)(((i+1))^2) (2^i).

Seja (Subscript[Q, n])=(∑_(i=1)^n)(((i+1))^2) (2^i).

Então tem-se

(Subscript[Q, n+1])=(∑_(i=1)^(n+1))(((i+1))^2) (2^i)=((∑_(i=1)^n)(((i+1))^2) (2^i))+(((n+2))^2)(2^(n+1))=(Subscript[Q, n])+(((n+2))^2)(2^(n+1))=(Subscript[Q, n])+((n^2)+4n+4)(2^(n+1)).

Mas, por outro lado, também se tem

(Subscript[Q, n+1])=(∑_(i=1)^(n+1))(((i+1))^2) (2^i)=(((1+1))^2)((.2)^1)+((∑_(i=2)^(n+1))(((i+1))^2) (2^i))=8+((∑_(i=1)^n)(((i+2))^2) (2^(i+1)))=8+2(∑_(i=1)^n)((i^2)+4i+4) (2^i)=8+2(∑_(i=1)^n)((i^2)+2i+1+2i+3) (2^i)=
8+2(∑_(i=1)^n)((((i+1))^2)+2i+3) (2^i)=8+2(∑_(i=1)^n)(((i+1))^2) (2^i)+2(∑_(i=1)^n)(2i+3) (2^i)=8+2(Subscript[Q, n])+4(∑_(i=1)^n)i (2^i)+6(∑_(i=1)^n)(2^i)=8+2(Subscript[Q, n])+4(2+(n-1)(2^(n+1)))+12 ((1-(2^n))/(1-2))=
8+2(Subscript[Q, n])+8+4(n-1)(2^(n+1))+12 ((2^n)-1)=2(Subscript[Q, n])+16+8(n-1)(2^n)+(12.2^n)-12=2(Subscript[Q, n])+4+4(2n+1)(2^n).

Logo

(Subscript[Q, n])+((n^2)+4n+4)(2^(n+1))=2(Subscript[Q, n])+4+4(2n+1)(2^n),

donde segue que

(Subscript[Q, n])=((n^2)+4n+4)(2^(n+1))-4-4(2n+1)(2^n)=(2(n^2)+8n+8-8n-4)(2^n)-4=(2(n^2)+4)(2^n)-4=((n^2)+2)(2^(n+1))-4

Grupo III (2.0 val)

Considere o programa f definido abaixo. Faça a análise detalhada para o número de multiplicações efectuadas, quando f recebe como argumento uma matriz quadrada de números inteiros, apresentando no final a respectiva ordem de grandeza e sabendo que o cálculo de g[x,y] realiza x+y multiplicações.

f=Function[w,Module[{i,j,r,n},
        n=Length[w];
        a=1;
        i=1;
        While[i<=n,
          a=a+g[i,i];
          j=1;
          While[j<=i,
            a=a*g[i,j]*g[j,i];
            j=j+1
            ];
          i=i+1
          ];
        a
        ]];

O número de multiplicações, assumindo uma matriz quadrada n x n é

(∑_(i=1)^n)((i+i)+((∑_(j=1)^i)1+(i+j)+1+(j+i)))=(∑_(i=1)^n)(2i+2((∑_(j=1)^i)1+i+j))=2((∑_(i=1)^n)i)+2(∑_(i=1)^n)(((∑_(j=1)^i)1+i)+((∑_(j=1)^i)j))=

2((n(n+1))/2)+2((∑_(i=1)^n)i(1+i)+((i(i+1))/2))=n(n+1)+2((∑_(i=1)^n)i+(i^2)+(((i^2)+i)/2))=(n^2)+n+2((∑_(i=1)^n)(3/2)((i^2)+i))=(n^2)+n+3((∑_(i=1)^n)(i^2)+i)=
(n^2)+n+3(∑_(i=1)^n)(i^2)+3(∑_(i=1)^n)i=(n^2)+n+3(((n^3)/3)+((n^2)/2)+(n/6))+3((n(n+1))/2)=(n^2)+n+(n^3)+((3(n^2))/2)+(n/2)+((3(n^2))/2)+((3n)/2)=
(n^3)+(n^2)+((3(n^2))/2)+((3(n^2))/2)+n+(n/2)+((3n)/2)=(n^3)+4(n^2)+3n=O((n^3))

Isto porque, tomando (Subscript[T, n])=(∑_(i=1)^n)(i^3) se tem

(Subscript[T, n+1])=(∑_(i=1)^(n+1))(i^3)=((∑_(i=1)^n)(i^3))+(((n+1))^3)= (Subscript[T, n])+(n^3)+3(n^2)+3n+1

mas também

(Subscript[T, n+1])=(∑_(i=1)^(n+1))(i^3)=1+((∑_(i=2)^(n+1))(i^3))=1+((∑_(i=1)^n)(((i+1))^3))=1+((∑_(i=1)^n)(i^3)+3(i^2)+3i+1)=1+((∑_(i=1)^n)(i^3))+3((∑_(i=1)^n)(i^2))+3((∑_(i=1)^n)i)+((∑_(i=1)^n)1)=1+ (Subscript[T, n])+3((∑_(i=1)^n)(i^2))+3((n(n+1))/2)+n

pelo que

(∑_(i=1)^n)(i^2)=(((n^3)+3(n^2)+3n+1-1-3((n(n+1))/2)-n)/3)=(((n^3)+(3-(3/2))(n^2)+(2-(3/2))n)/3)=((n^3)/3)+((n^2)/2)+(n/6)