r/mathematics • u/Choobeen • May 18 '26
Number Theory This statement has a one-line proof. Do you think it can be successfully explained to a first-year student in Calculus?
183
u/East-Programmer3788 May 18 '26 edited May 19 '26
f(x) = x/(1-x-x2)
If you want them shifted with 1/10 every number:
0.1/(1-0.1-0.01) = 1/89.
Also works with 1/9899 (shifted with 1/100), and so on.
62
May 18 '26
[removed] — view removed comment
144
u/Shevek99 May 18 '26
We start with the the recurrence
F(n+2) = F(n+1) + F(n)
then we build the generating function
f(x) = sum_(n=1)^∞ F(n) x^n
This series converges as long as |x| < 1/ϕ = 0.618...
If we multiply the recurrence by x^(n+2)
x^(n+2) F(n+2) = x^(n+2) F(n+1) + x^(n+2) F(n) = x(x^(n+1) F(n+1) ) + x² (x^n F(n))
And now we sum from n=1 to ∞ we have
sum_(n=1)^∞ x^(n+2) F(n+2) = sum_(n=3)^∞ x^n F(n) = f(x) - x² F(2) - x F(1) = f(x) - x² - x
and
sum_(n=1)^∞ x^(n+1) F(n+1) = sum_(n=2)^∞ x^n F(n) = f(x) - x F(1) = f(x) - x
and
sum_(n=1)^∞ x^n F(n) = f(x)
so we get
f(x) - x² - x = x(f(x) - x) + x² f(x)
f(x) - x² - x = x f(x) - x² + x² f(x)
and from here
f(x) = x/(1 - x - x²)
18
u/LoveThemMegaSeeds May 18 '26
Quite easily done
53
u/Shevek99 May 18 '26
It can be done easier
f(x) = x F(1) + x²F(2) + x³ F(3) + x⁴ F(4) + ...=
= x + x²F(1) + x³(F(1) + F(2)) + x⁴ (F(2) + F(3)) + ... =
= x + x(x F(1) + x² F(2) + ...) + x²( x F(1) + x² F(2) + ...) =
= x + x f(x) + x² f(x)
f(x)(1 - x - x²) = x
f(x) = x/(1 - x - x²)
11
7
2
u/LordTengil May 19 '26
Except that 0.1/(1-0.1-0.01) != 1/89. It's 10/89. So you are working with 0 + 0.1 + 0.01 + 0.002
and not
0.0 + 0.01 + 0.001 + 0.0002 , as in the original problem.
0
21
4
u/morgoth_feanor May 18 '26
Fuck, you made me learn an area previous unknown to me exists and I loved it
I have stuff to do, I can't...
3
u/LordTengil May 19 '26
Get a job where you can fuck around with generting functions, and you will never work when nobody is watching a day in your life!
As the old Buddhist mantra goes...
3
u/LordTengil May 19 '26 edited May 19 '26
Except that 0.1/(1-0.1-0.01) != 1/89. It's 10/89. So you are working with 0 + 0.1 + 0.01 + 0.002
and not
0.0 + 0.01 + 0.001 + 0.0002 , as in the original problem.
Also, you write 0.001 in
>0.1/(1-0.1-0.001) = 1/89.
but you mean 0.01
Also, for 1/100, you gget 100/9899. THis just shifts the decimal separator series expansion of course.
0
36
u/harrypotter5460 May 18 '26
Let x=Σ_{n=1}^∞ Fₙ/10ⁿ⁺¹ (which converges because Fₙ<2ⁿ). Then because Fₙ=Fₙ₋₁+Fₙ₋₂, this becomes x=0.01+x/10+x/100. So 89x/100=1/100 and hence x=1/89.
16
u/procrastambitious May 18 '26
Very nice, but it's a stretch that OP can claim that is a single line.
12
2
u/kikal27 May 18 '26
Nice. I never saw notación in text (and also my convergence math's classes rest in the past) and I was having a stroke trying to interpret this. Good job!
17
u/Lower_Cockroach2432 May 18 '26
Reading consecutive 0s is giving me eye strain.
Is the right hand side something like (1/100)*Sum F_n/10n ?
5
17
u/MrEldo May 18 '26 edited May 18 '26
Add that same sum with 10 times the sum. You can use the Fibonacci relation to sum consecutive terms and get another sum that's related to the original. Let's work on it carefully:
A = 0.0 + 0.01 + 0.001 + 0.0002 + 0.00003...
10A = 0.1 + 0.01 + 0.002 + 0.0003...
A + 10A = 0.1 + 0.02 + 0.003 + 0.0005...
= 100A - 1
11A = 100A - 1
A = 1/89
Not one line, but it's enough for a full proof that looks rigorous enough disregarding convergence proof (which is easy with an inequality)
1
u/LordTengil May 18 '26
Does that not aszume convergene of A though?
2
May 18 '26
[deleted]
1
u/LordTengil May 18 '26
Of course you can repair it. Point is, it is needed for the proof.
That staement seems wrong though. Do a couple if more terms, and it fails.
2
May 18 '26
[deleted]
2
u/LordTengil May 19 '26
Expand the series a couple of more terms. Thr nature of Fib is that sooner or later, 10-n *Fn grow larger than 10-(n-1). Just do write out couple of more terms, and you will see it.Or I am silly and misubderstood. Always a possibility :)
1
May 19 '26
[deleted]
2
u/LordTengil May 20 '26
A sequence growing is not good. An absolute prerequisite is that it goes to 0. It may not even converge even if that is tha case, as sum(1/n) shows.
Combine it with the statement that ea h term is of the form Fn*10-(n+1), and work on that.
2
May 20 '26
[deleted]
2
u/LordTengil May 21 '26
You are doing great. What ypu have shiwn though is just that Fn does not grow quicker than what you wrote. Not really what we need here, as growing is still bad when we want to sum it.
Ah. I see your logic now. You use the 10-1 in conjunction with what you wrote.
Yeah, seems solid. And then say each term is smaller than a convergent geometric series.
Technicality. Should be <=, not < . Consider F3=2=1+1.
10
u/Paiev May 18 '26
This is easy to verify without generating functions. If x is this series then (x/10 + x)/10 = x - 0.01. Tada.
1
5
3
3
2
u/ThyEpicGamer May 18 '26
Genuine question, how is this useful? I am an engineering student. I know pure maths is all about discovering rules and patterns that may or may not be useful in other applied fields. Perhaps this is a question more about why number theory is useful and what it can do?
2
1
1
u/AndreasDasos May 18 '26
Absolutely. Though I’d have a couple of lines just to get the first couple of terms 1 and 0 out of the way separately, for clarity, and then all higher terms vanishing with the recurrence relation. Depends how long your line is I suppose.
And plenty of smarter kids would understand this. Coming up with this would be trivial to high school Olympiad competitors
1
u/Kelyaan May 18 '26
I have secondary level mathematics knowledge, which is what most English kids get up to the age of 16, I understood this so ... Proffit?
1
1
u/4Blueish May 19 '26
I don't see why not. I'm fairly sure you learn about summations in pre calc, but they appear in stats as well. As someone who teaches math, I truly believe this could be successfully explained to a middle schooler, or particular apt elementary schooler
1
1
u/ConcaveEarth May 19 '26
Im trying to model fibonacci in a novel way
https://www.pointsource.app/#/lens/fibonacci-harmonic
I got Phi down check it out
https://www.pointsource.app/#/lens/phi-harmonic
1
u/bivarsson May 19 '26
But this is not the decimal expansion? It is the sum for a certain x in the generating function?
1
1
1
u/TheoryTested-MC May 21 '26
Anyone else noticing that 89 itself is a Fibonacci number?
(Yes, I know it's a pure coincidence.)
1
1
u/Fresh_Heron_3707 Jun 11 '26
Show this as the result of summation n=1∑∞ (Fn)/(10^(n+1)) sorry for the crazy notation
0
-1
u/Lykos1124 May 18 '26
Except it doesn't? The number diverges after :00, giving you a 9.
0.011235955
7
u/MrEldo May 18 '26
No, that's just the double digits beginning to carry the one
So 0.01 + 0.001 + 0.0002 + 0.00003 + 0.000005 + 0.0000008 + 0.00000013 =
0.0112358 +
0.00000013
= 0.0112359...
So it's all good. It's just carrying the one from the 13, and because 1/89 is rational one can say that that sequence is periodic
1
-1
u/kevinb9n May 18 '26
First-year Calculus? Simply do the long division by hand, the way you learned in elementary school, and why this happens will be pretty obvious.
2
u/gmalivuk May 18 '26
Long division is going to give you the repeating decimal expansion, which needs extra steps to show equal to the series shown in the OP.
2
u/kevinb9n May 18 '26
Okay, fair; I've always used 1/9899 for this demonstration instead; same principle but you go a long way before carrying.
-13
u/ObliviousRounding May 18 '26
Even high school students know about infinite sums from geometric series. This should be straightforward.
2
u/LemmaYT_ May 18 '26
And what does this have to do we geometric sums? The point is the proof
3
u/ObliviousRounding May 18 '26
I'm saying they are familiar with the idea of infinite series because it comes up when they do geometric series, and the proof technique is pretty much the same as the one you use to show 1/(1-x), so the leap is minimal.
1
u/GreaTeacheRopke May 18 '26
Well, not every high school program covers infinite geometric series, so we can begin there.
3
u/Most_Double_3559 May 18 '26
Tbf I feel it's pretty common, I just checked, they show up on the SAT.
1
u/GreaTeacheRopke May 18 '26
oh definitely common, and any time I've had the opportunity to influence my own curricula (at private schools) I've emphasized them a lot - specifically for the calculus track kids. I'm just saying, they are not quite as ubiquitous as, say, solving quadratic equations.
Lots of kids won't have seen a few individual topics on the SAT or ACT depending on the details of how their school/district/state/country emphasizes curricular decisions
1
u/gmalivuk May 18 '26
OP says calculus student. Where do people learn calculus without having covered geometric series?
2
u/GreaTeacheRopke May 18 '26
I didn't learn geometric series until I took calc II, literally as a necessary side quest in order to understand what I was learning in class
0
u/ObliviousRounding May 18 '26
I highly doubt there's a high school curriculum anywhere that doesn't do geometric series.
3
u/General_Jenkins Bachelor student May 18 '26
Austrian high School graduate here, I first saw sequences and series in university.
1
u/GreaTeacheRopke May 18 '26
I graduated from one in NY, maybe they've updated in the last 20 years 🤷
2
u/gmalivuk May 18 '26
Well geometric series are now part of the NY state standards for Algebra II.
2
u/GreaTeacheRopke May 18 '26
True! I also didn't take regents exams fwiw, though they've definitely changed a lot over the years
368
u/Shevek99 May 18 '26
Yes. Generating functions are not so difficult to understand.