Ensino Superior

victorross2 · 07 Nov 2020, 15:26

Dada função F definida como:

F(N)=4F(N/2)+N

(F(1)=1

Suponha N=2^k, para k=1, 2, 3, ... obtenha, detalhadamente, a fórmula fechada para F.

Alguém pode me ajudar? Não consigo resolver essa questão de forma alguma

Mensagem não lidapor **AnthonyC** » 19 Out 2021, 18:55 · Mensagem não lida por **AnthonyC** » 19 Out 2021, 18:55

[tex3]F(N)=4F\(N\over2\)+N[/tex3]
Como [tex3]N=2^k[/tex3] , temos:
[tex3]F(2^k)=4F\(2^k\over2\)+2^k[/tex3]
[tex3]F(2^k)=4F\(2^{k-1}\)+2^k[/tex3]
Podemos utilizar duas formas de resolução: encontrar um padrão e provar por indução ou por funções geradoras.

1º Método: "Adivinhe e Prove";
Começamos calculando alguns [tex3]F(2^k)[/tex3] para poder ver se há algum padrão.
[tex3]F(1)=1[/tex3]
[tex3]F(2)=4F(1)+2=6[/tex3]
[tex3]F(4)=4F(2)+4=28[/tex3]
[tex3]F(8)=4F(4)+8=120[/tex3]
[tex3]F(16)=4F(8)+16=496[/tex3]
[tex3]F(32)=4F(16)+32=2016[/tex3]
Como estamos trabalhando com potências de 2, uma boa tentativa é supor que os números obtidos tem alguma relação com potências de 2. Explorando um pouco, podemos encontrar o seguinte:
[tex3]F(2)=6=8-2=2^3-2[/tex3]
[tex3]F(4)=28=32-4=2^5-4[/tex3]
[tex3]F(8)=120=128-8=2^7-8[/tex3]
[tex3]F(16)=496=512-16=2^9-16[/tex3]
[tex3]F(32)=2016=2048-32=2^{11}-32[/tex3]
Assim, podemos supor que o padrão é [tex3]F(2^k)=2^{2k+1}-2^k[/tex3] . Provemos então por indução:

Caso inicial: [tex3]k=1[/tex3]
Código: Selecionar tudoSHIFT+Click na eq = ZOOM
[tex3]k=1[/tex3]
;
[tex3]F(2^1)=6=2^3-2^1[/tex3]
Código: Selecionar tudoSHIFT+Click na eq = ZOOM
[tex3]F(2^1)=6=2^3-2^1[/tex3]
Hipótese de Indução: seja o padrão verdadeiro para [tex3]k=n[/tex3]
Código: Selecionar tudoSHIFT+Click na eq = ZOOM
[tex3]k=n[/tex3]
;
[tex3]F(2^n)=2^{2n+1}-2^{n}[/tex3]
Código: Selecionar tudoSHIFT+Click na eq = ZOOM
[tex3]F(2^n)=2^{2n+1}-2^{n}[/tex3]

Temos:
[tex3]F(2^{n+1})=4F(2^n)+2^{n+1}[/tex3]
Código: Selecionar tudoSHIFT+Click na eq = ZOOM
[tex3]F(2^{n+1})=4F(2^n)+2^{n+1}[/tex3]

[tex3]F(2^{n+1})=4(2^{2n+1}-2^{n})+2^{n+1}[/tex3]
Código: Selecionar tudoSHIFT+Click na eq = ZOOM
[tex3]F(2^{n+1})=4(2^{2n+1}-2^{n})+2^{n+1}[/tex3]

[tex3]F(2^{n+1})=2^{2n+3}-2^{n+2}+2^{n+1}[/tex3]
Código: Selecionar tudoSHIFT+Click na eq = ZOOM
[tex3]F(2^{n+1})=2^{2n+3}-2^{n+2}+2^{n+1}[/tex3]

[tex3]F(2^{n+1})=2^{2n+3}-2^{n+1}(2-1)[/tex3]
Código: Selecionar tudoSHIFT+Click na eq = ZOOM
[tex3]F(2^{n+1})=2^{2n+3}-2^{n+1}(2-1)[/tex3]

[tex3]F(2^{n+1})=2^{2n+3}-2^{n+1}[/tex3]
Código: Selecionar tudoSHIFT+Click na eq = ZOOM
[tex3]F(2^{n+1})=2^{2n+3}-2^{n+1}[/tex3]

[tex3]F(2^{n+1})=2^{2n+2+1}-2^{n+1}[/tex3]
Código: Selecionar tudoSHIFT+Click na eq = ZOOM
[tex3]F(2^{n+1})=2^{2n+2+1}-2^{n+1}[/tex3]

[tex3]F(2^{n+1})=2^{2(n+1)+1}-2^{n+1}[/tex3]
Código: Selecionar tudoSHIFT+Click na eq = ZOOM
[tex3]F(2^{n+1})=2^{2(n+1)+1}-2^{n+1}[/tex3]

Assim, provamos por indução que [tex3]F(2^k)=2^{2k+1}-2^k[/tex3].

2º Método: Funções geradoras;
Seja [tex3]\Phi(x)[/tex3] uma função definida por:
[tex3]\Phi(x)\equiv\sum_{k=0}^\infty F(2^k)x^k[/tex3]
Vamos manipular essa função:
[tex3]\Phi(x)=\sum_{k=0}^\infty F(2^k)x^k[/tex3]
[tex3]\Phi(x)=F(1)+\sum_{k=1}^\infty F(2^k)x^k[/tex3]
[tex3]\Phi(x)=1+\sum_{k=1}^\infty [4F(2^{k-1})+2^k]x^k[/tex3]
[tex3]\Phi(x)=1+\sum_{k=1}^\infty [4F(2^{k-1})x^k+2^kx^k][/tex3]
[tex3]\Phi(x)=1+\sum_{k=1}^\infty 4F(2^{k-1})x^k+\sum_{k=1}^\infty 2^kx^k[/tex3]
[tex3]\Phi(x)=1+4\sum_{k=1}^\infty F(2^{k-1})x^k+\sum_{k=1}^\infty (2x)^k[/tex3]
Podemos reconhecer o último somatório como sendo a soma de P.G. infinita com razão [tex3]2x[/tex3] e termo inicial [tex3]2x[/tex3]. Já no primeiro somatório, faremos a mudança de variável: [tex3]\begin{cases}
k-1=u \\
k=u+1 \\
k=1 \implies u=0\\
k\rightarrow \infty \implies u\rightarrow \infty
\end{cases}[/tex3]. Logo:
[tex3]\Phi(x)=1+4\sum_{u=0}^\infty F(2^{u})x^{u+1}+{2x\over1-2x}[/tex3]
[tex3]\Phi(x)=1+4x\sum_{u=0}^\infty F(2^{u})x^{u}+{2x\over1-2x}[/tex3]
Podemos ver que o somatório é exatamente a definição de [tex3]\Phi(x)[/tex3], logo:
[tex3]\Phi(x)=1+4x\Phi(x)+{2x\over1-2x}[/tex3]
[tex3]\Phi(x)-4x\Phi(x)=1+{2x\over1-2x}[/tex3]
[tex3]\Phi(x)(1-4x)=1+{2x\over1-2x}[/tex3]
[tex3]\Phi(x)={1\over1-4x}+{2x\over(1-2x)(1-4x)}[/tex3]
Utilizando a técnica de frações parciais, podemos separar o último termo em duas frações:
[tex3]{2x\over(1-2x)(1-4x)}={A\over1-2x}+{B\over1-4x}[/tex3]
[tex3]{2x\over(1-2x)(1-4x)}={A(1-4x)+B(1-2x)\over(1-2x)(1-4x)}[/tex3]
[tex3]{2x}={A(1-4x)+B(1-2x)}[/tex3]
[tex3]{2x}={A+B +x(-4A-2B)}[/tex3]
Igualando os coeficientes dos polinômios:
[tex3]\begin{cases}
A+B=0\implies A=-B \\
-4A-2B=2\implies A=-1\implies B=1
\end{cases}[/tex3]
Logo:
[tex3]{2x\over(1-2x)(1-4x)}={-1\over1-2x}+{1\over1-4x}[/tex3]
Assim, temos:
[tex3]\Phi(x)={1\over1-4x}+{2x\over(1-2x)(1-4x)}[/tex3]
[tex3]\Phi(x)={1\over1-4x}+{-1\over1-2x}+{1\over1-4x}[/tex3]
Vemos que cada um dos termos é da forma [tex3]a_0\over1-r[/tex3]. Portanto, podemos transforma-los em somas de P.G. infinitas:
[tex3]\Phi(x)=\sum_{k=0}^\infty(4x)^k+\sum_{k=0}^\infty-(2x)^k+\sum_{k=0}^\infty(4x)^k[/tex3]
[tex3]\Phi(x)=\sum_{k=0}^\infty[(4x)^k-(2x)^k+(4x)^k][/tex3]
[tex3]\Phi(x)=\sum_{k=0}^\infty[2(4x)^k-(2x)^k][/tex3]
[tex3]\Phi(x)=\sum_{k=0}^\infty[2(4)^k-2^k]x^k[/tex3]
[tex3]\Phi(x)=\sum_{k=0}^\infty[2(2^2)^k-2^k]x^k[/tex3]
[tex3]\Phi(x)=\sum_{k=0}^\infty[2^{2k+1}-2^k]x^k[/tex3]
[tex3]\sum_{k=0}^\infty F(2^k)x^k=\sum_{k=0}^\infty[2^{2k+1}-2^k]x^k[/tex3]
Igualando os coeficientes:
[tex3]F(2^k)=2^{2k+1}-2^k[/tex3]

Ensino Superior ⇒ Fórmula fechada Tópico resolvido

Fórmula fechada

Re: Fórmula fechada

Ensino Superior ⇒ Fórmula fechada Tópico resolvido

Fórmula fechada

Re: Fórmula fechada

Entrar | Registrar