Ambos saem rápido por indução "forte". A ideia é, dada uma certa propriedade p(n), mostrar que:
a) p(1) é verdadeira b) (Para k=2,3,...) se p(n) é verdadeira para n=1,2,3,...,k-1, então p(k) é verdadeira. De (a) e (b), por indução forte, conclui-se que p(n) é verdadeira para todo n natural positivo. ---///--- Detalhes: 1) a) 1= 2^0 é soma de potências distintas de 2 (bom, onde entendemos "soma" dum jeito amplo, permitindo uma única parcela) b) Suponha que qualquer número abaixo de k pode ser escrito como soma de potências de 2 distintas. Agora procure a maior potência de 2 que "cabe" em k, isto é, encontre m tal que 2^m<=k<2^(m+1). Se k = 2^m; acabou, esta é a "soma" que procurávamos; senão A=k-2^m pode ser escrito como soma de potências distintas de 2. Mas A<2^(m+1)-2^m=2^m, ou seja, nenhuma destas potências pode ser 2^m. Assim, k=A+2^m é soma de potências **distintas** de 2. 2) a) 1=F_1 é soma de números de Fibonacci. b) Suponha que qualquer número abaixo de k pode ser escrito como soma de F_n distintos. Agora procure o maior F_n que "cabe" em k, isto é, encontre F_m tal que F_m<=k<F_(m+1). Se k = F_m; acabou, esta é a "soma" que procurávamos; senão A=k-F_m pode ser escrito como soma de números de Fibonacci distintos. Mas A<F_(m+1)-F_m=F_(m-1)<F_m, ou seja, nenhum destes números pode ser F_m (nem F_(m-1)). Assim, k=A+F_m é soma de números de Fibonacci distintos (de fato, mostramos que esta soma não contém dois F_m "consecutivos"!). Abraço, Ralph. 2015-03-26 21:15 GMT-03:00 marcone augusto araújo borges < marconeborge...@hotmail.com>: > 1) Prove que todo número natural pode ser representado como soma de > diversas potências distintas de base 2 > > 2) Prove que qualquer número natural pode ser representado como a soma de > diversos números de Fibonacci diferentes > > -- > Esta mensagem foi verificada pelo sistema de antivírus e > acredita-se estar livre de perigo. > -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
