Define F(n) as the number of ways to express a natural number n as a sum of 1's and 2's. Order matters.
Example F(4)=5 from 4 = 1+1+1+1 = 2+1+1 = 1+2+1 = 1+1+2 = 2+2.
Define G(n) as the number of ways to express a natural number n as a sum of odd natural numbers. Order matters.
Example G(4)=3 from 4 = 1+1+1+1 = 1+3 = 3+1
Evaluate the limit of F(n)/G(n) as n goes to infinity.
F(n) = 1 + (n-1) + C(n-2,2) + C(n-3,3) + ...
... + C(ceil(n/2),floor(n/2))
= C(n-0,0) + C(n-1,1) + C(n-2,2) + C(n-3,3) + ...
... + C(ceil(n/2),floor(n/2))
G(n) is hard to describe in this closed form. It's best expressed as a recursive algorithm. Starting with either n or n-1 (depending on odd or even n) and going to smaller numbers to 1, zero or as many as will fit inthe remainder are tried, and continue with the remaider after that so all branches are reached:
for n=3:20
F=0;
for i=0:floor(n/2)
F=F+nchoosek(n-i,i);
end
fprintf('%3d %7d',n,F)
g=G(n);
fprintf('%7d %14.12f\n',g,F/g)
end
function gval=G(x)
global ways remain dens qtys
ways=0; goal=x; remain=x; dens=[]; qtys=[];
forms(x);
gval=ways;
end
function forms(st)
global ways remain dens qtys
den=st;
if mod(den,2)==0
den=den-1;
end
for q=0:floor(remain/den)
if q>0
dens(end+1)=den;
qtys(end+1)=q;
end
remain=remain-q*den;
if remain==0
ways=ways+factorial(sum(qtys))/prod(factorial(qtys));
else
forms(den-2);
end
remain=remain+q*den;
if q>0
dens(end)=[];
qtys(end)=[];
end
end
end
n F(n) G(n) F(n)/G(n)
3 3 2 1.500000000000
4 5 3 1.666666666667
5 8 5 1.600000000000
6 13 8 1.625000000000
7 21 13 1.615384615385
8 34 21 1.619047619048
9 55 34 1.617647058824
10 89 55 1.618181818182
11 144 89 1.617977528090
12 233 144 1.618055555556
13 377 233 1.618025751073
14 610 377 1.618037135279
15 987 610 1.618032786885
16 1597 987 1.618034447822
17 2584 1597 1.618033813400
18 4181 2584 1.618034055728
19 6765 4181 1.618033963167
20 10946 6765 1.618033998522
G(n) is the nth Fibonacci number while F(n) is the (N+1)st Fibonacci number, so the ratio of the latter to the former approaches the Golden Ratio.
|
|
Posted by Charlie
on 2023-11-16 09:46:42 |
solution
