tag:blogger.com,1999:blog-4115025577315673827.post5322413885404891331..comments2019-05-18T16:40:30.584+05:30Comments on CSE Blog - quant, math, computer science puzzles: Fibonacci Multiple PuzzleUnknownnoreply@blogger.comBlogger8125tag:blogger.com,1999:blog-4115025577315673827.post-81598682653805389262015-09-09T17:26:34.821+05:302015-09-09T17:26:34.821+05:30Any fibonacci number could be written as sum of an...Any fibonacci number could be written as sum of any two (lower) value of fibonacci numbers. for example:<br /><br />f(10) = f(9) + f(8)<br /> = 2f(8) + f(7)<br /> = 3f(7) + 2f(6)<br /> and so on..<br /><br />So, if we split f(nk) it could be written as<br /><br /> f(nk) = x1*f(k+1) + x2*f(k)<br /> <br />These coefficients also follows fibonacci pattern. For example:<br /><br /> f(10) = f(2)*f(10-1) + f(1)*f(10-2)<br /> = f(3)*f(10-2) + f(2)*f(10-3)<br /> = f(4)*f(10-3) + f(3)*f(10-4)<br /> and so on...<br /><br />therefore x1 will be equals to f((n-1)k)<br /><br />now the equation could be written as:<br /><br /> f(nk) = f((n-1)k)*f(k+1) + x2*f(k)<br /><br />which could be re-written as<br /><br />f(nk) = [ f((n-1)k) ] *f(k+1) + x2*f(k)<br /> = [ x3*f(k+1) + x4*f(k) ] * f(k+1) + x2*f(k)<br /> = [ f((n-2)k)*f(k+1) + x4*f(k) ] * f(k+1) + x2*f(k)<br /><br />and so on...<br />and the final equation would be like:<br /><br /> f(nk) = f(k)*a1*f(k+1) + a2*f(k)<br /> = f(k) [ a1*f(k+1) + a2 ]<br /> <br />and at one point the coefficient of f(k+1) will be a multiple of f(k).<br />Hence every f(nk) has f(k) as its factor.Nehahttps://www.blogger.com/profile/18312939491551541514noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-40918040805023229832015-01-31T06:00:04.689+05:302015-01-31T06:00:04.689+05:30F(n+1) = F(n-1)+F(n) F(n+2) = F(n-1)+2F(n) F(n+3)=...F(n+1) = F(n-1)+F(n)<br />F(n+2) = F(n-1)+2F(n)<br />F(n+3)= 2F(n-1)+3F(n)<br />.<br />.<br />.<br />F(n+k)=F(k)F(n-1)+F(k+1)F(n) -- 1<br />so, F(2n) = F(n)F(n-1)+F(n+1)F(n) = t*F(n)<br />induction: <br />assume F(nk) = L*F(n) ( since we proved F(2n) = t*F(n))<br />F(n(k+1)) = F(nk+n)=F(n)F(nk-1)+F(n+1)(F(nk) = L*F(n))<br />rhs is divisible by F(n)nitin siwachhttps://www.blogger.com/profile/04752930302372361487noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-52176997655164930872015-01-29T15:49:16.670+05:302015-01-29T15:49:16.670+05:30Assume that F(nK) is a multiple of F(K). We shall ...Assume that F(nK) is a multiple of F(K). We shall prove that F((n+1)K) is also a multiple of F(K).<br /><br />F(nK+2) = F(nK+1) + F(nK)<br />F(nK+3) = F(nK+2) + F(nK+1) = 2F(nK+1) + F(nK)<br />F(nK+4) = F(nK+3) + F(nK+2) = 3F(nK+1) + 2F(nK)<br />F(nK+5) = F(nK+4) + F(nK+3) = 5F(nK+1) + 3F(nK)<br />F(nK+6) = F(nK+5) + F(nK+4) = 8F(nK+1) + 5F(nK)<br />.<br />.<br />.<br />F(nK+i) = F(i) F(nK+1) + F(i-1) F(nK)<br /><br />Thus, when i=K, we have F((n+1)K) = F(K) F(nK+1) + F(K-1) F(nK), which is a multiple of F(K) as both terms are multiples of F(K) (recall that F(nK) is a multiple of F(K)).Mathewhttps://www.blogger.com/profile/12414167735806085812noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-7355966080059720932015-01-26T22:01:24.275+05:302015-01-26T22:01:24.275+05:30Here is a brute force method: its well known th...Here is a brute force method: <br /><br />its well known that F(n)= [a^n-b^n]/sqrt (5) where a= (1+sqrt(5))/2 and b= (1-sqrt(5))/2.<br />so its required to prove that [a^(n*k)-b^(n*k)]/(a^k-b^k) is a whole number.<br /><br />in fact a little algebra shows that above expression is a whole number for natural n and k ,and real numbers a and b , provided a+b and a*b are whole numbers.<br /><br />outline of proof:<br />let x=a^k and y=b^k.<br />prove by induction , that x^i+y^i is a whole number for any natural i.<br />its clear that for natural i , (x*y)^i is also a whole number as a*b is a whole number.<br /><br />expression of interest = [x^n-y^n]/[x-y].<br />=sigma (x^i)* y^(n-1-i), i = 0 to n-1.<br />if n is even, the expression equals sigma (x*y)^i * [ (x^(n-1-2*i)+y^(n-1-2*i) ], i = 0 to (n-2)/2<br />if n is odd , the expression equals (x*y)^((n-1)/2) +sigma (x*y)^i * [ (x^(n-1-2*i)+y^(n-1-2*i) ], i = 0 to (n-3)/2.<br /><br />hence proved as (x*y)^i and x^i+y^i are whole numbers for all natural numbers i. cherahttps://www.blogger.com/profile/15883972329291461469noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-42334540161241849422015-01-24T08:07:20.600+05:302015-01-24T08:07:20.600+05:30Lemma: For 0 &lt;= k &lt; n: F(n) = F(k+1) * F(n-k...Lemma:<br />For 0 &lt;= k &lt; n:<br />F(n) = F(k+1) * F(n-k) + F(k) * F(n-k-1)<br /><br />This can be proven by induction on k.<br />base case k = 0:<br />F(n) = 1 * F(n) + 0 * F(n-1)<br /><br />induction:<br />Since F(n-k) = F(n-k-1) + F(n-k-2), one can rearrange coefficients, so that<br />F(n) = F(k+1) * F(n-k) + F(k) * F(n-k-1)<br />F(n) = F(k+1) * (F(n-k-1) + F(n-k-2)) + F(k) * F(n-k-1)<br />F(n) = (F(k+1) + F(k)) * F(n-k-1) + F(k+1) * F(n-k-2)<br />F(n) = F(k+2) * F(n-k-1) + F(k+1) * F(n-k-2)<br /><br /><br />To finish, use induction on n to show that F(n*K) is a multiple of F(K).<br />base case n = 0:<br />F(0) = 0 is a multiple of F(K)<br /><br />induction:<br />By the lemma,<br />F((n+1)*K) = F(K+1) * F(n*K) + F(K) * F(n*K-1)<br />and since both F(n*K) and F(K) are multiple of K, so is F((n+1)*K)Félix de Chaumont Quitryhttps://www.blogger.com/profile/02724420621332283916noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-71103720217883646602015-01-22T11:14:10.636+05:302015-01-22T11:14:10.636+05:30We prove this using induction. Before that, we mak...We prove this using induction. Before that, we make a small observation about Fibonacci numbers<br /><br />For any positive integer k,<br />F(k+2) = F(k+1) + F(k)<br />F(k+3) = 2*F(k+1) + F(k)<br />F(K+4) = 3*F(k+1) + 2*F(k)<br />...<br />F(k+m) = F(m)*F(k+1) + F(m-1)*F(k)<br />where m is a positive integer<br /><br />We need to prove that for a positive integers K and n, F(n*K) = c*F(K) where c is a positive integer.<br />Setting K to be any positive integer, and applying induction on n,<br />The base case is n = 1. F(K) = 1*F(K). Thus the base case holds.<br />Assuming the statement is true for some n. F(n*K) = c*F(K)<br />Now,<br />F((n+1)*K) = F(n*K+K) = F(K)*F(n*K+1) + F(K-1)*F(n*K)<br />But F(n*K) = c*F(K).<br />Thus F((n+1)*K) = F(K)*(F(n*K+1)+c*F(K-1)) = c&#39;*F(K) where c&#39; is a positive integer<br />Thus the induction holds.<br /><br />The given statement is true for all positive integers K and n.Prajwalhttps://www.blogger.com/profile/11945090524272193777noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-17634421913645447922015-01-22T10:56:01.099+05:302015-01-22T10:56:01.099+05:30Use the formula for F_n given here. https://www.ma...Use the formula for F_n given here. https://www.math.hmc.edu/funfacts/ffiles/10002.4-5.shtml<br /><br />Also, a-b divides a^n-b^n. Let a=Phi^k and b=phi^k. Observe that the factor (a^n-b^n)/(a-b) is an integer.GoKuhttps://www.blogger.com/profile/05674743004147477362noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-20935280836624455812015-01-22T04:19:26.697+05:302015-01-22T04:19:26.697+05:30Lemma. F(n) = F(k+1).F(n-k) + F(k).F(n-k-1) Proof....Lemma. F(n) = F(k+1).F(n-k) + F(k).F(n-k-1)<br />Proof.<br />F(n)<br />= F(2).F(n-1) + F(1).F(n-2)<br />= F(3).F(n-2) + F(2).F(n-3)<br />= ...<br />= F(k+1).F(n-k) + F(k).F(n-k-1)<br /><br />Now for proof of the main question, suppose F(k) divides F((n-1)k) [inductive hypothesis].<br />From above lemma, we have,<br />F(n.k) = F(k+1).F((n-1).k) + F(k).F((n-1)k - 1)<br />Since F(k) divides F((n-1)k), F(k) divides F(n.k).<br />QEDPritishhttps://www.blogger.com/profile/04147166709938295125noreply@blogger.com