{"id":7806,"date":"2010-04-08T07:00:00","date_gmt":"2010-04-08T07:00:00","guid":{"rendered":"http:\/\/xmau.com\/wp\/notiziole\/2010\/04\/08\/fibonacci_e_la\/"},"modified":"2010-04-08T07:00:00","modified_gmt":"2010-04-08T07:00:00","slug":"fibonacci_e_la","status":"publish","type":"post","link":"https:\/\/xmau.com\/wp\/notiziole\/2010\/04\/08\/fibonacci_e_la\/","title":{"rendered":"Fibonacci e la ricorsione"},"content":{"rendered":"<div class='__iawmlf-post-loop-links' style='display:none;' data-iawmlf-post-links='[{&quot;id&quot;:9972,&quot;href&quot;:&quot;http:\\\/\\\/xmau.com\\\/notiziole\\\/arch\\\/201003\\\/006437.html&quot;,&quot;archived_href&quot;:&quot;http:\\\/\\\/web-wp.archive.org\\\/web\\\/20150616093342\\\/http:\\\/\\\/xmau.com\\\/notiziole\\\/arch\\\/201003\\\/006437.html&quot;,&quot;redirect_href&quot;:&quot;&quot;,&quot;checks&quot;:[{&quot;date&quot;:&quot;2026-02-17 04:56:36&quot;,&quot;http_code&quot;:206},{&quot;date&quot;:&quot;2026-02-25 18:09:00&quot;,&quot;http_code&quot;:206},{&quot;date&quot;:&quot;2026-03-16 11:35:44&quot;,&quot;http_code&quot;:206},{&quot;date&quot;:&quot;2026-03-20 03:53:40&quot;,&quot;http_code&quot;:206},{&quot;date&quot;:&quot;2026-03-27 19:37:21&quot;,&quot;http_code&quot;:206},{&quot;date&quot;:&quot;2026-04-01 20:58:43&quot;,&quot;http_code&quot;:206},{&quot;date&quot;:&quot;2026-04-10 15:30:19&quot;,&quot;http_code&quot;:503},{&quot;date&quot;:&quot;2026-04-20 11:14:33&quot;,&quot;http_code&quot;:206},{&quot;date&quot;:&quot;2026-04-24 08:51:28&quot;,&quot;http_code&quot;:206}],&quot;broken&quot;:false,&quot;last_checked&quot;:{&quot;date&quot;:&quot;2026-04-24 08:51:28&quot;,&quot;http_code&quot;:206},&quot;process&quot;:&quot;done&quot;}]'><\/div>\n<p>Ricordate il problema che <a href=\"http:\/\/xmau.com\/notiziole\/arch\/201003\/006437.html\">avevo postato<\/a> il mese scorso, in cui si chiedeva di dimostrare che ogni numero intero pu\u00f2 essere espresso in uno e un solo modo come somma di numeri di Fibonacci distinti e non consecutivi? Avevo dato una dimostrazione per induzione, ma avevo aggiunto che non avrei mai scelto di dimostrarlo in questo modo perch\u00e9 il tutto mi pareva inutilmente involuto. Adesso vi presento la &#8220;mia&#8221; soluzione, presentata in modo descrittivo seguendo il ragionamento che ho effetivamente fatto: come vedrete, \u00e8 un misto di ricorsione e induzione.<br \/>\nInnanzitutto ho iniziato a scrivere i primi numeri che corrispondono alle ipotesi in &#8220;base Fibonacci&#8221;. Detto in altro modo, proprio come 2718 in base 10 equivale a 8*10<sup>0<\/sup> + 1*10<sup>1<\/sup> + 7*10<sup>2<\/sup> + 2*10<sup>3<\/sup>, 2718 in base Fibonacci &ndash; che scriver\u00f2 come 2718<sub>F<\/sub> &ndash; equivale a 8*F(1) + 1*F(2) + 7*F(3) + 2*F(4), cio\u00e8 8*1 + 1*2 + 7*3 + 2*5 = 41. I numeri esprimibili come somma di numeri di Fibonacci distinti e non consecutivi, se scritti in base Fibonacci, saranno composti da soli zero e uno, senza avere mai due uno consecutivi. Ho iniziato cos\u00ec a scrivere i primi di questi numeri, mettendo a fianco il valore corrispondente in base 10.<br \/>\n<tt>1<sub>F<\/sub> = 1<\/tt><br \/>\n<tt>10<sub>F<\/sub> = 2<\/tt><br \/>\n<tt>100<sub>F<\/sub> = 3<\/tt><br \/>\n<tt>101<sub>F<\/sub> = 4<\/tt><br \/>\n<tt>1000<sub>F<\/sub> = 5<\/tt><br \/>\n<tt>1001<sub>F<\/sub> = 6<\/tt><br \/>\n<tt>1010<sub>F<\/sub> = 7<\/tt><br \/>\n<tt>10000<sub>F<\/sub> = 8<\/tt><br \/>\n<tt>10001<sub>F<\/sub> = 9<\/tt><br \/>\n<tt>10010<sub>F<\/sub> = 10<\/tt><br \/>\n<tt>10100<sub>F<\/sub> = 11<\/tt><br \/>\n<tt>10101<sub>F<\/sub> = 12<\/tt><br \/>\nMi sono subito accorto di una cosa fantastica: abbiamo scritto una e una sola volta tutti i numeri da 1 a 12! Visto che il numero successivo, 100000<sub>F<\/sub>, \u00e8 gi\u00e0 13, posso immaginare che questo pattern continui all&#8217;infinito. A questo punto mi sono messo a cercare una formula ricorsiva per vedere quanti e quali sono i numeri di <i>k<\/i> cifre in base Fibonacci che soddisfino i vincoli. A parte i casi banali con <i>k<\/i> &le; 2, un numero di <i>k<\/i> cifre inizia con il prefisso 10 e continua usando tutti i numeri con al pi\u00f9 <i>k-2<\/i> cifre (compreso 0). Il numero di questi numeri \u00e8 F<sub><i>k-2<\/i><\/sub> (per ipotesi induttiva); visto che quelli con meno di <i>k<\/i> cifre sono F<sub><i>k-1<\/i><\/sub> (sempre per ipotesi induttiva), la loro somma \u00e8 proprio F<sub><i>k<\/i><\/sub>. Siamo cos\u00ec riusciti a costruire ricorsivamente tutti i numeri con al pi\u00f9 <i>k<\/i> cifre in base Fibonacci che soddisfino i vincoli, e abbiamo scoperto che li abbiamo trovati tutti (e non ce ne sono di uguali, perch\u00e9 se <i>m<\/i><sub>F<\/sub> e <i>n<\/i><sub>F<\/sub> sono diversi, 10<i>m<\/i><sub>F<\/sub> e 10<i>n<\/i><sub>F<\/sub> sono anche diversi).<br \/>\nIl tutto \u00e8 ricorsione oppure no? Qualche passaggio induttivo l&#8217;ho usato, e del resto il mio amico gnugnu dice che secondo lui ricorsione, induzione e discesa infinita &ndash; una tecnica di dimostrazione per assurdo che Fermat apprezzava molto ma che \u00e8 davvero complicata da usare &ndash; sono poi la stessa cosa. Il mio pragmatismo \u00e8 un po&#8217; diverso: io vedo i vari metodi in maniera diversa, e trovo appunto una dimostrazione come questa essenzialmente pi\u00f9 &#8220;visuale&#8221; di una prettamente induttiva. Inoltre in questo modo uno si convince del risultato, e riesce anche a capire come possa averlo trovato a chi ha proposto il teorema; sicuramente l&#8217;enunciato standard non ve l&#8217;avrebbe mai fatto venire in mente.<br \/>\nVoi che ne pensate?<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Come (ri)dimostrare un teorema in maniera pi\u00f9 civile.<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_lmt_disableupdate":"","_lmt_disable":"","jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"activitypub_content_warning":"","activitypub_content_visibility":"","activitypub_max_image_attachments":3,"activitypub_interaction_policy_quote":"anyone","activitypub_status":"","footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[214],"tags":[],"class_list":["post-7806","post","type-post","status-publish","format-standard","hentry","category-matematica_light"],"modified_by":null,"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p6hcSh-21U","jetpack-related-posts":[{"id":7805,"url":"https:\/\/xmau.com\/wp\/notiziole\/2010\/04\/01\/ricorsione\/","url_meta":{"origin":7806,"position":0},"title":"Ricorsione","author":".mau.","date":"2010-04-01","format":false,"excerpt":"due parole sulla ricorsione, o come si pu\u00f2 definire una cosa per mezzo di s\u00e9 stessa.","rel":"","context":"In &quot;matematica_light&quot;","block_context":{"text":"matematica_light","link":"https:\/\/xmau.com\/wp\/notiziole\/category\/matematica_light\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":7749,"url":"https:\/\/xmau.com\/wp\/notiziole\/2010\/03\/11\/fibonacci_e_lin\/","url_meta":{"origin":7806,"position":1},"title":"Fibonacci e l&#8217;induzione","author":".mau.","date":"2010-03-11","format":false,"excerpt":"un teorema sui numeri di Fibonacci dimostrabile con l'induzione","rel":"","context":"In &quot;matematica_light&quot;","block_context":{"text":"matematica_light","link":"https:\/\/xmau.com\/wp\/notiziole\/category\/matematica_light\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":33876,"url":"https:\/\/xmau.com\/wp\/notiziole\/2025\/10\/01\/base-fibonacci-insieme-di-shevelev-e-congettura-di-kimberling\/","url_meta":{"origin":7806,"position":2},"title":"Base Fibonacci, insieme di Shevelev e congettura di Kimberling","author":".mau.","date":"2025-10-01","format":false,"excerpt":"Un'ennesima strana caratteristica dei numeri di Fibonacci","rel":"","context":"In &quot;mate-light-2025&quot;","block_context":{"text":"mate-light-2025","link":"https:\/\/xmau.com\/wp\/notiziole\/category\/matematica_light\/matelight-2025\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":6092,"url":"https:\/\/xmau.com\/wp\/notiziole\/2008\/06\/04\/giochi_matemati\/","url_meta":{"origin":7806,"position":3},"title":"Giochi matematici del Medioevo (libro)","author":".mau.","date":"2008-06-04","format":false,"excerpt":"Uno sguardo sulla storia della matematica attraverso il Liber Abaci","rel":"","context":"In &quot;recensioni&quot;","block_context":{"text":"recensioni","link":"https:\/\/xmau.com\/wp\/notiziole\/category\/recensioni\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":14263,"url":"https:\/\/xmau.com\/wp\/notiziole\/2017\/01\/13\/topolino-e-fibonacci\/","url_meta":{"origin":7806,"position":4},"title":"Topolino e Fibonacci","author":".mau.","date":"2017-01-13","format":false,"excerpt":"Questa non me l'aspettavo dalla Disney","rel":"","context":"In &quot;povera_matematica&quot;","block_context":{"text":"povera_matematica","link":"https:\/\/xmau.com\/wp\/notiziole\/category\/povera_matematica\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/notiziole\/wp-content\/uploads\/sites\/6\/2017\/01\/topolino-mole-150x150.jpg?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":31636,"url":"https:\/\/xmau.com\/wp\/notiziole\/2025\/03\/05\/il-rapporto-superaureo-3\/","url_meta":{"origin":7806,"position":5},"title":"Il rapporto superaureo &#8211; 3","author":".mau.","date":"2025-03-05","format":false,"excerpt":"Ultima parte della trattazione sul numero superaureo, con un (immancabile?) frattale.","rel":"","context":"In &quot;mate-light-2025&quot;","block_context":{"text":"mate-light-2025","link":"https:\/\/xmau.com\/wp\/notiziole\/category\/matematica_light\/matelight-2025\/"},"img":{"alt_text":"frattale di Rauzy","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/notiziole\/wp-content\/uploads\/sites\/6\/2025\/03\/Supergolden_Rauzy_sqr.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]}],"jetpack_likes_enabled":true,"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/xmau.com\/wp\/notiziole\/wp-json\/wp\/v2\/posts\/7806","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/xmau.com\/wp\/notiziole\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/xmau.com\/wp\/notiziole\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/xmau.com\/wp\/notiziole\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/xmau.com\/wp\/notiziole\/wp-json\/wp\/v2\/comments?post=7806"}],"version-history":[{"count":0,"href":"https:\/\/xmau.com\/wp\/notiziole\/wp-json\/wp\/v2\/posts\/7806\/revisions"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/wp\/notiziole\/wp-json\/wp\/v2\/media?parent=7806"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/wp\/notiziole\/wp-json\/wp\/v2\/categories?post=7806"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/wp\/notiziole\/wp-json\/wp\/v2\/tags?post=7806"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}