Função Composta com expressão de recursividade
27 mai 2012, 19:22
Seja f uma função definida no conjunto dos INTEIROS NÃO NEGATIVOS que satisfaz as seguintes condições:
I) f(1) = 1
II) f(2n) = 2 . f(n) + 1, se n ≥ 1
III) f(f(n)) = 4n + 1, se n ≥ 2
Determine f(1993):
I) f(1) = 1
II) f(2n) = 2 . f(n) + 1, se n ≥ 1
III) f(f(n)) = 4n + 1, se n ≥ 2
Determine f(1993):
Re: Função Composta
28 mai 2012, 14:56
Olá Daniel
Esta é bem puxada
Vou pôr os cálculos que fiz até agora
de II)
\(f(2n) = 2 . f(n) + {1} \\\\ substitutindo \ n \ por \ 2n \\\\ f(4n)=2f(2n)+{1}=2(2 . f(n) + {1})+{1} =4f(n)+3\\ f(8n)=2f(4n)+{1}=2(4f(n)+3)+{1}=8f(n)+7\\ f(16n)=2(8n)+{1}=2(8f(n)+7)+{1}=16f(n)+15\\\\ generalizando\\\\ f(32n)=2f(16n)+{1}=\\ =2(16f(n)+15)+1=\\ =32f(n)+2.(2.7+1)+1=\\ =32f(n)+2.(2.(2.(2+1)+{1})+{1})+{1}\\\\ continuando \ a \ generalizar\\\\ f(2^k)=2^k+{2}.({2}.({2}.({2}.(.....)...+{1})+{1})+{1})+{1}=\\ =2^k+{2}.{2}.{2}.{2}....+{8}+{4}+{2}+{1}=\\ =2^k+2^{k-1}+\sum_{i=0}^{k-2}2^i=\\ =2^k+2^{k-1}+\frac{1-2^{k-1}}{{1}-{2}}=\\ ={2}.2^k-{1}\\\\ entao\\\\ f(2^k)={2}.2^k-{1}\)
Esta é bem puxada
Vou pôr os cálculos que fiz até agora
de II)
\(f(2n) = 2 . f(n) + {1} \\\\ substitutindo \ n \ por \ 2n \\\\ f(4n)=2f(2n)+{1}=2(2 . f(n) + {1})+{1} =4f(n)+3\\ f(8n)=2f(4n)+{1}=2(4f(n)+3)+{1}=8f(n)+7\\ f(16n)=2(8n)+{1}=2(8f(n)+7)+{1}=16f(n)+15\\\\ generalizando\\\\ f(32n)=2f(16n)+{1}=\\ =2(16f(n)+15)+1=\\ =32f(n)+2.(2.7+1)+1=\\ =32f(n)+2.(2.(2.(2+1)+{1})+{1})+{1}\\\\ continuando \ a \ generalizar\\\\ f(2^k)=2^k+{2}.({2}.({2}.({2}.(.....)...+{1})+{1})+{1})+{1}=\\ =2^k+{2}.{2}.{2}.{2}....+{8}+{4}+{2}+{1}=\\ =2^k+2^{k-1}+\sum_{i=0}^{k-2}2^i=\\ =2^k+2^{k-1}+\frac{1-2^{k-1}}{{1}-{2}}=\\ ={2}.2^k-{1}\\\\ entao\\\\ f(2^k)={2}.2^k-{1}\)
Re: Função Composta
29 mai 2012, 15:19
Olá,
Esta parece-me uma questão de olimpíadas.
\(\begin{array}{cll}
f(1993) &=f(4*498+1)&\\
&=f(f(f(498))) & \mbox{por III}\\
&=f(f(2f(249)+1)) & \mbox{por II}\\
&=4(2f(249)+1)+1 & \mbox{por III}\\
&=8f(249)+5 &\\
&=8f(4*62+1)+5 &\\
&=8f(f(f(62)))+5 & \mbox{por III}\\
&=8(4f(62)+1)+5 & \mbox{por III}\\
&=32f(62)+13 & \\
&=32(2f(31)+1)+13 & \mbox{por II}\\
&=64f(31)+45 & \\
&=64f(2*2^4-1)+45 & \\
&=64f(f(2^4))+45 & \mbox{pela formula do Joao}\\
&=64(4*2^4+1)+45 &\\
&=4205&\mbox{se nao me enganei nos calculos}
\end{array}\)
Esta parece-me uma questão de olimpíadas.
\(\begin{array}{cll}
f(1993) &=f(4*498+1)&\\
&=f(f(f(498))) & \mbox{por III}\\
&=f(f(2f(249)+1)) & \mbox{por II}\\
&=4(2f(249)+1)+1 & \mbox{por III}\\
&=8f(249)+5 &\\
&=8f(4*62+1)+5 &\\
&=8f(f(f(62)))+5 & \mbox{por III}\\
&=8(4f(62)+1)+5 & \mbox{por III}\\
&=32f(62)+13 & \\
&=32(2f(31)+1)+13 & \mbox{por II}\\
&=64f(31)+45 & \\
&=64f(2*2^4-1)+45 & \\
&=64f(f(2^4))+45 & \mbox{pela formula do Joao}\\
&=64(4*2^4+1)+45 &\\
&=4205&\mbox{se nao me enganei nos calculos}
\end{array}\)
Re: Função Composta
29 mai 2012, 15:40
Muito obrigado caro Rui Carpentier por mais uma magna contribuição
Confesso que não chegava lá
Saudações matemáticas
Confesso que não chegava lá
Saudações matemáticas
Re: Função Composta
29 mai 2012, 16:04
Mas assim o enunciado estaria errado (o que eu também pensei logo):
\(f(f(n)) = 4\mathbf{f}(n) + 1\)
e não
\(f(f(n)) = 4n + 1\)
\(f(f(n)) = 4\mathbf{f}(n) + 1\)
e não
\(f(f(n)) = 4n + 1\)
Re: Função Composta
29 mai 2012, 16:15
josesousa Escreveu:Mas assim o enunciado estaria errado (o que eu também pensei logo):
\(f(f(n)) = 4\mathbf{f}(n) + 1\)
e não
\(f(f(n)) = 4n + 1\)
Como assim caro José Sousa?
Os cálculos foram feitos com base em f(f(n)) = 4n + 1
Re: Função Composta com expressão de recursividade
29 mai 2012, 16:26
Tem razão, caro amigo João.
Com tantos f(n), f(f(n)) e afins, quase troquei os olhos.
Excelente resolução!
Com tantos f(n), f(f(n)) e afins, quase troquei os olhos.
Excelente resolução!
Re: Função Composta com expressão de recursividade
02 jun 2012, 19:36
Muito obrigado a todos!
Daniel.
Daniel.