{"id":7749,"date":"2010-03-11T07:00:00","date_gmt":"2010-03-11T07:00:00","guid":{"rendered":"http:\/\/xmau.com\/wp\/notiziole\/2010\/03\/11\/fibonacci_e_lin\/"},"modified":"2010-03-11T07:00:00","modified_gmt":"2010-03-11T07:00:00","slug":"fibonacci_e_lin","status":"publish","type":"post","link":"https:\/\/xmau.com\/wp\/notiziole\/2010\/03\/11\/fibonacci_e_lin\/","title":{"rendered":"Fibonacci e l&#8217;induzione"},"content":{"rendered":"<div class='__iawmlf-post-loop-links' style='display:none;' data-iawmlf-post-links='[{&quot;id&quot;:9979,&quot;href&quot;:&quot;http:\\\/\\\/xmau.com\\\/notiziole\\\/arch\\\/201003\\\/006416.html&quot;,&quot;archived_href&quot;:&quot;http:\\\/\\\/web-wp.archive.org\\\/web\\\/20150616130755\\\/http:\\\/\\\/xmau.com\\\/notiziole\\\/arch\\\/201003\\\/006416.html&quot;,&quot;redirect_href&quot;:&quot;&quot;,&quot;checks&quot;:[{&quot;date&quot;:&quot;2026-02-17 05:15:38&quot;,&quot;http_code&quot;:206},{&quot;date&quot;:&quot;2026-02-27 10:40:15&quot;,&quot;http_code&quot;:206},{&quot;date&quot;:&quot;2026-03-07 08:59:51&quot;,&quot;http_code&quot;:206},{&quot;date&quot;:&quot;2026-03-17 16:42:16&quot;,&quot;http_code&quot;:206},{&quot;date&quot;:&quot;2026-03-21 05:20:03&quot;,&quot;http_code&quot;:206},{&quot;date&quot;:&quot;2026-03-25 13:32:28&quot;,&quot;http_code&quot;:206},{&quot;date&quot;:&quot;2026-03-29 21:43:21&quot;,&quot;http_code&quot;:206},{&quot;date&quot;:&quot;2026-04-03 14:54:43&quot;,&quot;http_code&quot;:206}],&quot;broken&quot;:false,&quot;last_checked&quot;:{&quot;date&quot;:&quot;2026-04-03 14:54:43&quot;,&quot;http_code&quot;:206},&quot;process&quot;:&quot;done&quot;}]'><\/div>\n<p>Leggendo quanto <a href=\"http:\/\/xmau.com\/notiziole\/arch\/201003\/006416.html\">ho scritto sull&#8217;induzione<\/a>, Gnugnu mi ha scritto, suggerendomi un teorema che si pu\u00f2 dimostrare con l&#8217;induzione forte: ogni intero pu\u00f2 essere scritto in un unico modo come somma di numeri di Fibonacci distinti e non consecutivi. Per chi non se lo ricordasse, i numeri di Fibonacci sono definiti cos\u00ec: F<sub>1<\/sub> = F<sub>2<\/sub> = 1, e poi F<sub><i>n<\/i>+1<\/sub> = F<sub><i>n<\/i><\/sub> + F<sub><i>n<\/i>-1<\/sub>. In questo caso, per\u00f2, i primi due numeri di Fibonacci non sono 1 e 1 ma 1 e 2, in modo che tutti i numeri siano distinti. Se volete provare a dimostrare il teorema, smettete di leggere ora! Se invece della dimostrazione non ve ne pu\u00f2 importare nulla, saltate i due paragrafi seguenti che sono s\u00ec semplici, ma anche piuttosto noiosi.<br \/>\nPer dimostrare che una cosa si pu\u00f2 fare in un solo modo, in genere si inizia a domostrare che la si pu\u00f2 fare, e poi si fa vedere che se la si fa in due modi questi sono in realt\u00e0 lo stesso. Vediamo allora innanzitutto che ogni numero pu\u00f2 essere scritto come somma di numeri di Fibonacci distinti e non consecutivi. I casi 1, 2 e 3 sono banali: la &#8220;somma&#8221; \u00e8 il singolo numero stesso. Andiamo avanti, e prendiamo un <i>n<\/i> qualunque. Sia F<sub><i>k<\/i><\/sub>=<i>f<\/i> il pi\u00f9 grande numero di Fibonacci minore o uguale a <i>n<\/i>. Se <i>f<\/i>=<i>n<\/i> siamo a posto; altrimenti sia <i>d<\/i>=<i>n<\/i>&#8211;<i>f<\/i>. Sicuramente <i>d<\/i>&lt;<i>f<\/i>, visto che tranne nel caso di 1 e 2 ciascun numero di Fibonacci \u00e8 minore del doppio del precedente; cerchiamo ora il pi\u00f9 grande numero di Fibonacci minore o uguale a <i>d<\/i>. Tale numero non pu\u00f2 essere  F<sub><i>k<\/i>-1<\/sub>, perch\u00e9 altrimenti se <i>n<\/i> &ge; F<sub><i>k<\/i><\/sub>+F<sub><i>k<\/i>-1<\/sub> allora \u00e8 maggiore o uguale a F<sub><i>k<\/i>+1<\/sub>, contro la nostra ipotesi. Ma <i>d<\/i> \u00e8 esprimibile come somma di numeri di Fibonacci distinti e non consecutivi per ipotesi induttiva, quindi siamo a posto per quanto riguarda la prima parte.<br \/>\nE per la seconda? Beh, prendiamo il pi\u00f9 piccolo numero <i>n<\/i> esprimibile in due modi diversi come somma di numeri di Fibonacci distinti e non consecutivi. Il pi\u00f9 grande F<sub><i>k<\/i><\/sub> nello sviluppo dei due numeri deve essere per forza diverso: altrimenti anche <i>n<\/i>-F<sub><i>k<\/i><\/sub> sarebbe esprimibile in due modi diversi, e quindi <i>n<\/i> non sarebbe il pi\u00f9 piccolo. A questo punto ci occorre un lemma che mostri come &ndash; per quanto grande possa essere un numero come da ipotesi il cui sviluppo abbia come termine maggiore F<sub><i>k<\/i><\/sub> &ndash; sar\u00e0 sempre strettamente minore di F<sub><i>k<\/i>+1<\/sub>. Di nuovo, possiamo usare l&#8217;induzione. 1, 2, 3 non danno problemi perch\u00e9 il loro sviluppo contiene un solo numero. Per un <i>k<\/i> generico, un numero <i>m<\/i> il cui sviluppo abbia come termine maggiore F<sub><i>k<\/i><\/sub> avr\u00e0 al pi\u00f9 come secondo termine F<sub><i>k<\/i>-2<\/sub>; quindi per ipotesi induttiva <i>m<\/i> &#8211; F<sub><i>k<\/i><\/sub> &lt; F<sub><i>k<\/i>-1<\/sub> da cui <i>m<\/i> &lt; F<sub><i>k<\/i><\/sub> + F<sub><i>k<\/i>-1<\/sub> = F<sub><i>k<\/i>+1<\/sub>, come volevasi dimostrare.<br \/>\nDal lemma otteniamo cos\u00ec che non \u00e8 nemmeno possibile che i due modi diversi per esprimere <i>n<\/i> abbiano come maggior numero di Fibonacci nel loro sviluppo due numeri diversi, e quindi la nostra tesi \u00e8 ottenuta.<br \/>\nDetto tutto questo, e dando il bentornato a chi non ha avuto voglia di infilarsi in quei conti che sembravano essere infiniti, aggiungo che se io dovessi presentare una dimostrazione di questo teorema la farei in maniera completamente diversa e, almeno a mio parere, molto pi\u00f9 intuitiva. Per\u00f2 prima di farla mi tocca fare qualche altro post&#8230;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>un teorema sui numeri di Fibonacci dimostrabile con l&#8217;induzione<\/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-7749","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-20Z","jetpack-related-posts":[{"id":7806,"url":"https:\/\/xmau.com\/wp\/notiziole\/2010\/04\/08\/fibonacci_e_la\/","url_meta":{"origin":7749,"position":0},"title":"Fibonacci e la ricorsione","author":".mau.","date":"2010-04-08","format":false,"excerpt":"Come (ri)dimostrare un teorema in maniera pi\u00f9 civile.","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":7203,"url":"https:\/\/xmau.com\/wp\/notiziole\/2009\/06\/27\/fiboprodotti\/","url_meta":{"origin":7749,"position":1},"title":"FiboProdotti","author":".mau.","date":"2009-06-27","format":false,"excerpt":"Un bel problemino matematico con una soluzione meno complicata di quanto possa sembrare.","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":7805,"url":"https:\/\/xmau.com\/wp\/notiziole\/2010\/04\/01\/ricorsione\/","url_meta":{"origin":7749,"position":2},"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":7733,"url":"https:\/\/xmau.com\/wp\/notiziole\/2010\/03\/08\/linduzione_mate_1\/","url_meta":{"origin":7749,"position":3},"title":"L&#8217;induzione matematica [2\/2]","author":".mau.","date":"2010-03-08","format":false,"excerpt":"seconda parte delle spiegazioni sull'induzione matematica.","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":7749,"position":4},"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":7732,"url":"https:\/\/xmau.com\/wp\/notiziole\/2010\/03\/05\/linduzione_mate\/","url_meta":{"origin":7749,"position":5},"title":"L&#8217;induzione matematica [1\/2]","author":".mau.","date":"2010-03-05","format":false,"excerpt":"che cos'\u00e8 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":[]}],"jetpack_likes_enabled":true,"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/xmau.com\/wp\/notiziole\/wp-json\/wp\/v2\/posts\/7749","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=7749"}],"version-history":[{"count":0,"href":"https:\/\/xmau.com\/wp\/notiziole\/wp-json\/wp\/v2\/posts\/7749\/revisions"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/wp\/notiziole\/wp-json\/wp\/v2\/media?parent=7749"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/wp\/notiziole\/wp-json\/wp\/v2\/categories?post=7749"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/wp\/notiziole\/wp-json\/wp\/v2\/tags?post=7749"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}