Teste 1 
Matemática Discreta LEIC 2008/2009

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 n≥0, (∑_(i=0)^n)(i/(2^i))=2-((n+2)/(2^n)).

Base de indução (n=0)

	(∑_(i=0)^0)(i/(2^i))=(0/(2^0))=(0/1)=0=2-2=2-(2/1)=2-((0+2)/(2^0))

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

Tese:(∑_(i=0)^(n+1))(i/(2^i))=2-((n+3)/(2^(n+1)))

(∑_(i=0)^(n+1))(i/(2^i))=((∑_(i=0)^n)(i/(2^i)))+((n+1)/(2^(n+1)))(Subscript[=, HI])2-((n+2)/(2^n))+((n+1)/(2^(n+1)))=2+((-2n-4+n+1)/(2^(n+1)))=2+((-n-3)/(2^(n+1)))=2-((n+3)/(2^(n+1)))

Grupo II (2.5 val)

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

Tem-se que (∑_(i=1)^(n+1))(((((i-1))^2)/(2^i))+2(n-(i-1)))=((∑_(i=1)^(n+1))((((i-1))^2)/(2^i)))+2((∑_(i=1)^(n+1))(n-(i-1)))=((∑_(i=0)^n)((i^2)/(2^(i+1))))+2((∑_(i=0)^n)i)

onde o segundo somatório é de uma progressão aritmética, pelo que se obtém

(1/2)((∑_(i=0)^n)((i^2)/(2^i)))+2n((n+1)/2)=(1/2)((∑_(i=0)^n)((i^2)/(2^i)))+(n^2)+n

onde o somatório pode ser resolvido por perturbação, tal como justificado abaixo, obtendo-se

(1/2)(6-(((n^2)+4n+6)/(2^n)))+(n^2)+n=3-(((n^2)+4n+6)/(2^(n+1)))+(n^2)+n

* Seja (Subscript[T, n])=(∑_(i=0)^n)((i^2)/(2^i)).

Então tem-se

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

Por outro lado, também se tem

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

podendo o primeiro somatório resolvido usando o resultado do Grupo I e sendo o segundo de uma progressão geométrica.

Logo

(Subscript[T, n])+(((n^2)+2n+1)/(2^(n+1)))=
(1/2)(Subscript[T, n])+((∑_(i=0)^n)(i/(2^i)))+(1/2)((∑_(i=0)^n)((((1/2)))^i))=(1/2)(Subscript[T, n])+2-((n+2)/(2^n))+(1/2).((1-((((1/2)))^(n+1)))/(1-(1/2)))=(1/2)(Subscript[T, n])+2-((n+2)/(2^n))+(1/2)(((1-((((1/2)))^(n+1)))/(1/2)))=(1/2)(Subscript[T, n])+2-((n+2)/(2^n))+1-(1/(2^(n+1)))=(1/2)(Subscript[T, n])+3-((2n+4+1)/(2^(n+1)))=(1/2)(Subscript[T, n])+3-((2n+5)/(2^(n+1))),

donde segue que

(Subscript[T, n])=2(3-((2n+5)/(2^(n+1)))-(((n^2)+2n+1)/(2^(n+1))))=6-((2n+5+(n^2)+2n+1)/(2^n))=6-(((n^2)+4n+6)/(2^n))

Grupo III (2.0 val)

Considere o programa f definido abaixo.

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

(a) 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[w, x] realiza (2^x) multiplicações.

O número de multiplicações corresponde ao somatório (∑_(i=1)^n)(2+(2^(i+1))+((∑_(j=1)^i)(2^(i-j))))=((∑_(i=1)^n)2)+((∑_(i=1)^n)(2^(i+1)))+((∑_(i=1)^n)(∑_(j=1)^i)(2^(i-j)))=2n+4((1-(2^n))/(1-2))+((∑_(i=1)^n)(∑_(j=0)^(i-1))(2^j))=2n+4((2^n)-1)+((∑_(i=1)^n)((1-(2^i))/(1-2)))=2n+(2^(n+2))-4+((∑_(i=1)^n)(2^i)-1)=2n+(2^(n+2))-4+((∑_(i=1)^n)(2^i))-((∑_(i=1)^n)1)=2n+(2^(n+2))-4+2((1-(2^n))/(1-2))-n=n+(2^(n+2))+(2^(n+1))-6=n+(2^(n+1))(2+1)-6=n+(3.2^(n+1))-6

(b) Conclua que assimptoticamente a quantidade calculada na alínea (a) relativamente a uma matriz n×n é O((2^n)).

Queremos verificar que n+(3.2^(n+1))-6=O((2^n)).

De facto, basta verificar que 

	(Subscript[lim , n -> ∞])  ((n+(3.2^(n+1))-6)/(2^n))=((Subscript[lim , n -> ∞])  (n/(2^n)))+((Subscript[lim , n -> ∞])  ((3.2^(n+1))/(2^n)))-((Subscript[lim , n -> ∞])  (6/(2^n)))=0+((Subscript[lim , n -> ∞])  6)-0=6
e portanto para qualquer ϵ>0 existe k tal que se n≥k então |((n+(3.2^(n+1))-6)/(2^n))-6|≤ ϵ.

Logo,((n+(3.2^(n+1))-6)/(2^n))-6≤|((n+(3.2^(n+1))-6)/(2^n))-6|≤ϵ donde se conclui que n+(3.2^(n+1))-6≤ (ϵ+6)((.2)^n) para n≥k.