-
Notifications
You must be signed in to change notification settings - Fork 0
/
Fibonacci.html
149 lines (121 loc) · 11.2 KB
/
Fibonacci.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
<!DOCTYPE html>
<html lang="fi">
<head>
<meta charset="UTF-8">
<!-- Begin Jekyll SEO tag v2.5.0 -->
<title>Fibonaccin luvut ja binomikertoimet | Matematiikkakilpailijat</title>
<meta name="generator" content="Jekyll v3.8.5" />
<meta property="og:title" content="Fibonaccin luvut ja binomikertoimet" />
<meta name="author" content="Valtteri Aurela" />
<meta property="og:locale" content="fi" />
<meta name="description" content="Matematiikan olympiavalmennuksen osallistujien kokemuksia" />
<meta property="og:description" content="Matematiikan olympiavalmennuksen osallistujien kokemuksia" />
<link rel="canonical" href="https://blog-drafts.matematiikkakilpailut.fi/Fibonacci.html" />
<meta property="og:url" content="https://blog-drafts.matematiikkakilpailut.fi/Fibonacci.html" />
<meta property="og:site_name" content="Matematiikkakilpailijat" />
<meta property="fb:app_id" content="964806940344711" />
<script type="application/ld+json">
{"url":"https://blog-drafts.matematiikkakilpailut.fi/Fibonacci.html","author":{"@type":"Person","name":"Valtteri Aurela"},"headline":"Fibonaccin luvut ja binomikertoimet","description":"Matematiikan olympiavalmennuksen osallistujien kokemuksia","@type":"WebPage","@context":"http://schema.org"}</script>
<!-- End Jekyll SEO tag -->
<meta name="viewport" content="width=device-width, initial-scale=1">
<meta name="theme-color" content="#157878">
<link href='https://fonts.googleapis.com/css?family=Open+Sans:400,700' rel='stylesheet' type='text/css'>
<link rel="stylesheet" href="/assets/css/style.css?v=2c669b5e01ecebd0ccd9a63f1cd21eeeb0cf1936">
<link href="/feed.xml" type="application/atom+xml" rel="alternate" title="Sivuston verkkosyöte">
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
tex2jax: {
inlineMath: [['$', '$'], ['\\(', '\\)']],
displayMath: [['$$', '$$']],
processEscapes: true
}
});
</script>
<script
type="text/javascript" async
src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-AMS_CHTML"
integrity="sha256-nvJJv9wWKEm88qvoQl9ekL2J+k/RWIsaSScxxlsrv8k="
crossorigin="anonymous">
</script>
<link href="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/fonts/HTML-CSS/TeX/woff/MathJax_Main-Regular.woff"
rel="preload" as="font" type="font/woff" crossorigin="anonymous">
<link href="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/fonts/HTML-CSS/TeX/woff/MathJax_Size1-Regular.woff"
rel="preload" as="font" type="font/woff" crossorigin="anonymous">
<link href="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/fonts/HTML-CSS/TeX/woff/MathJax_Math-Italic.woff"
rel="preload" as="font" type="font/woff" crossorigin="anonymous">
<link href="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/fonts/HTML-CSS/TeX/woff/MathJax_Size2-Regular.woff"
rel="preload" as="font" type="font/woff" crossorigin="anonymous">
</head>
<body>
<section class="page-header">
<h1 class="project-name">Matematiikkakilpailijat</h1>
<h2 class="project-tagline">Matematiikan olympiavalmennuksen osallistujien kokemuksia</h2>
</section>
<section class="main-content">
<article class="post">
<header class="post-header">
<h1 class="post-title">Fibonaccin luvut ja binomikertoimet</h1>
</header>
<section class="post-content">
<p><strong>Postauksen tarkoitus</strong>
Tässä postauksessa käsitellään mielenkiintoista yhteyttä Fibonaccin lukujen ja binomikertoimien välillä. Saman tuloksen saamiseen on monta eri keinoa, mutta käymme tässä läpi mukavan kombinatorisen todistuksen ja hieman motiiveja välivaiheiden takana.</p>
<p><strong>1. Tarvittavat pohjatiedot</strong>
Koska todistus on hyvin alkeellinen, ei paljoakaan etukäteistietoja tarvita. Jonkinlainen kästiys binomikertoimien käyttötarkoituksista tarvitaan, sillä ne ovat tärkeä osa todistettavaa väitettä ja ilman niitä viimeinen osa saattaa jäädä hieman epäselväksi.</p>
<p>Jos jokin asia jää mietityttämään, kannattaa käydä välivaihe itse läpi siten, että ymmärtää sen täysin. Tämäntyyppinen miettiminen on hyvin kehittävää.</p>
<p><strong>2. Todistettava muoto</strong>
Kun keksin alunperin tämän todistuksen, en yrittänyt todistaa seuraavaksi esitettävää väitettä. Todistus tapahtui puoliksi vahingossa tutkiessani, mitä tapahtuisi, jos muuttaisin Fibonaccin lukuja kombinatoriseen muotoon. Haluan kuitenkin kertoa ensiksi mihin “tähtäämme”, jotta olisi helpompi miettiä kokonaisuudessa, mitä tapahtuu.</p>
<p>Määritellään $F_n$ on $n$:nnes Fibonaccin luku. Nyt pätee, että <script type="math/tex">F_n = \sum\limits_{i\leq \frac{n}{2} } {n-i \choose i}</script></p>
<p><strong>3. Todistus</strong>
Todistus voi lähteä aluksi hieman erikoisen näköiseen suuntaan, mutta palaa kuitenkin asiaan. Tulokseen kyllä päästään tekstin loppuun mennessä.</p>
<p><strong>Lemma 1.</strong>
$n$:nnes Fibonaccin luku voidaan ajatella tapojen määränä heittää kaksipuolisella nopalla silmälukujen summaksi $n$. Nopan silmäluvut ovat 1 ja 2, ja heittojen määrää ei ole rajoitettu. Eri permutaatiot ovat sallittuja.</p>
<p><strong>Todistus</strong>
Jotta olisi selvää, mitä tässä tapahtuu, käymme läpi esimerkin. Luku 3 voidaan heittää seuraavilla tavoilla
(1,1,1), (1,2), (2,1)</p>
<p>Kolmelle ensimmäiselle $n$:n arvolle tavat ovat:</p>
<p>0: (): $1 = F_0$
1: (1): $1 = F_1$
2: (1,1), (2): $2 = F_2$</p>
<p>Lista jatkuu samalla tavalla. Mutta miten tämä voidaan todistaa?</p>
<p>Luodaan lukujono $G$, jossa $G_n$ kertoo kuinka monella tavalla voidaan heittää $n$ lemman 1 mukaisesti. Pyritään saamaan tälle jokin rekursiivinen muoto. Huomaamme, että tämä onnistuu hyvin luontevasti. Tapoja heittää $n$ tällä tavalla on yhtä monta kuin tapoja heittää $n-1$ lisättynä tapoihin heittää $n-2$. Mistä tämä johtuu? Tulos tulee suoraan siitä, että summaan $n$ voidaan päästä ainoastaan kahdella tavalla, heittämällä 1 tilanteessa $n-1$ tai heittämällä 2 tilanteessa $n-2$. Saamme siis $G_n = G_{n-1} + G_{n-2}$.</p>
<p>Tämä näyttää tutulta. Jos katsomme Fibonaccin lukujen määritelmää, huomaamme samankaltaisuuden. Koska $F_n = F_{n-1} + F_{n-2}$ ja $F_0 = G_0$, $F_1 = G_1$, nämä lukujonot ovat identtisiä.</p>
<p>Mutta mitä hyötyä lemma 1:stä sitten on? Huomaamme, että kaikki kelvolliset silmälukujen 1 ja 2 heittojen määrät ovat yhtälön $2x + y = n$ kokonaislukuratkaisuja, kun $n$ on jokin vakio. Tästä saamme kaikki toimivat määrät, mutta permutaatiot ovat vielä läpikäymättä.</p>
<p>Oletetaan nyt, että olemme heittäneet $x$ kappaletta lukua kaksi ja $y$ kappaletta lukua yksi. Tämähän on vain erillaisten tapojen määrä järjestää kahden numeron lukujono, kun tiedämme paljonko kumpaakin numeroa on. Vaihtoehtoja on ${ x+y \choose x } = \frac{(x+y)!}{x!\cdot y!}$. Summaamalla tälläiset luvut kaikilla toimivilla $x$ ja $y$, saamme kaikki permutaatioiden määrät eli siis myös Fibonaccin luvun.</p>
<p>Jos kuitenkin katsomme todistettavaa lauseketta, huomaamme, että siellä ei ollut muuttujaa $y$ tai muutenkaan kahta muuttujaa. On kuitenkin helppoa vähentää johtamastamme kaavasta muuttujien määrä yhteen muuttujaan (ja vakioon). Pätee nimittäin selvästi, että jos $2x + y = n$ niin $x + y = n - x$ ja nyt meillä on luvussa $x+y \choose x$ yläkerrassa oleva luku esitetty muodossa, missä on vain yksi muuttuja sekä $n$. Lopullinen yksittäinen termi on siis $n-x \choose x$.</p>
<p>Ratkaisuja, joissa $x > \frac{n}{2}$ ei ole, sillä $x$ ja $y$ ovat positiivisia kokonaislukuja. Tämän takia meidän täytyy summata vain ensimmäiset $\frac{n}{2}$ termiä. Katsotaan, miltä tämä summa näyttäisi. Haluammme summata kaikki $n-x \choose x$, jolloin saamme kaavan <script type="math/tex">F_n = \sum\limits_{x\leq \frac{n}{2} } {n-x \choose x }</script></p>
<p>Mutta tämähän on oikea kaava! Olemme siis valmiita.</p>
<p><strong>4. Motiiveja todistuksen takana</strong>
Koska alunperin en yrittänyt todistaa juuri tätä kaavaa, saatoin edetä todistuksessa kiinnostavalta näyttävään suuntaan, ilman pakkoa päästä tiettyyn tulokseen. Keksin siis oikeastaan väitteen todistuksen pohjalta. Todistus on loppujen lopuksi hyvin suoraviivainen, kun on löytänyt yhteyden nopan heittojen ja Fibonaccin lukujen välillä. Sen jälkeen tehtävä on vain vähän kombinatoriikkaa ja kaavan muotoilemista, jotta summa saataisiin todistettavan väitteen muotoon.</p>
</section>
<footer class="post-footer">
<p><time datetime=""></time>
• Valtteri Aurela
<span class="share-buttons">
<a href="https://www.facebook.com/sharer/sharer.php?u=https%3A%2F%2Fblog-drafts.matematiikkakilpailut.fi%2FFibonacci.html"e=Fibonaccin+luvut+ja+binomikertoimet"
title="Jaa Facebookissa" target="_blank" rel="noopener noreferrer nofollow">
<svg aria-label="Jaa Facebookissa" role="img" viewBox="0 0 24 24"><title lang="en">Facebook</title><use xlink:href="/assets/images/icons.svg#facebook"/></svg></a>
<a href="https://twitter.com/intent/tweet?url=https%3A%2F%2Fblog-drafts.matematiikkakilpailut.fi%2FFibonacci.html&text=Fibonaccin+luvut+ja+binomikertoimet"
target="_blank" rel="noopener noreferrer nofollow" title="Jaa Twitterissä">
<svg aria-label="Jaa Twitterissä" role="img" viewBox="0 0 24 24"><title lang="en">Twitter</title><use xlink:href="/assets/images/icons.svg#twitter"/></svg></a>
<a href="https://pinterest.com/pin/create/button/?url=https%3A%2F%2Fblog-drafts.matematiikkakilpailut.fi%2FFibonacci.html&description=Fibonaccin+luvut+ja+binomikertoimet"
target="_blank" rel="noopener noreferrer nofollow" title="Jaa Pinterestissä">
<svg aria-label="Jaa Pinterestissä" role="img" viewBox="0 0 24 24"><title lang="en">Pinterest</title><use xlink:href="/assets/images/icons.svg#pinterest"/></svg></a>
<a href="https://www.reddit.com/submit?url=https%3A%2F%2Fblog-drafts.matematiikkakilpailut.fi%2FFibonacci.html&title=Fibonaccin+luvut+ja+binomikertoimet"
target="_blank" rel="noopener noreferrer nofollow" title="Jaa Redditissä">
<svg aria-label="Jaa Redditissä" role="img" viewBox="0 0 24 24"><title lang="en">Reddit</title><use xlink:href="/assets/images/icons.svg#reddit"/></svg></a>
<a href="https://www.linkedin.com/shareArticle?mini=true&url=https%3A%2F%2Fblog-drafts.matematiikkakilpailut.fi%2FFibonacci.html&title=Fibonaccin+luvut+ja+binomikertoimet&source=https%3A%2F%2Fblog-drafts.matematiikkakilpailut.fi"
target="_blank" rel="noopener noreferrer nofollow" title="Jaa LinkedInissä">
<svg aria-label="Jaa Linkedinissä" role="img" viewBox="0 0 24 24"><title lang="en">LinkedIn</title><use xlink:href="/assets/images/icons.svg#linkedin"/></svg></a>
<a href="https://pinboard.in/add?url=https%3A%2F%2Fblog-drafts.matematiikkakilpailut.fi%2FFibonacci.html&title=Fibonaccin+luvut+ja+binomikertoimet"
target="_blank" rel="noopener noreferrer nofollow" title="Talleta Pinboardiin">
<svg aria-label="Talleta Pinboardiin" role="img" viewBox="0 0 24 24"><title lang="en">Pinboard</title><use xlink:href="/assets/images/icons.svg#pinboard"/></svg></a>
</span>
</p>
</footer>
</article>
</section>
<section class="site-footer">
<p>Tekijänoikeus kirjoittajilla. Käytämme sivuilla evästeitä: <a href="/tietosuoja.html">tietosuojalauseke</a>.</p>
</section>
</body>
</html>