That was a really interesting problem. It combined some analysis and number theory. I'm going to have to go back over it a couple of times though. I don't think I quite understand why the f'(x) is fine at 0. As well as some other things.
I think because f(x) was the limit of f_n(x) with x in the numerator so f(0)=0 and the derivative is well behaved because nothing in the denominator will be 0 for x=0
I know this problem. D. Woods is Don Woods. We were office-mates in grad school. He showed me the problem some time later, probably in the 90's. I have considered proposing this problem as a possible video. I hoped it would include the real analysis to show that f(x) is well-defined (ie, that the sequences do converge), continuous (except at poles at some negative integers), and differentiable. I guess my hoped for target audience is undergrads currently taking real analysis.
2:35 I think the point of the denominator being f_n(x+2^n) needs more justification, I see why it is correct since the next denominator term would be x+4, but I think it would be helpful to further include other terms in order to make this solution clearer.
I suggest to read the paper, even if it is a bit laconic. Many details have to be rebuilt. a) the proof of the convergence is based on a fundamental theorem of product sequences with factors of the form 1+a_n: such product converges iff the series with a_n terms is absolutely convergent; as a matter of fact, the factors of the functions f_k(x) can be associated in quartets, according to the 4-module remaind; with immediate algebra it is easy to rearrange any of this quadruple factor as (1+a_n) with a_n being a o(1/n^2) term as the natural index n tends to infinity; therefore the convergence can be grounded on the basis of the abovementioned general condition for infinite products. b) it is immediately verified that such convergence is uniform with respect to the x variable; in fact, the terms a_n are functions of x, i.e. let a_n(x), and it can be easily checked that the convergence of the series with a_n(x) terms is uniform ; so the convergence of the infinite product with factors 1+a_n; c) f(0)=0 because of the first factor of the infinite product i.e. x; any other factors is non-zero for x=0; therefore we can let f(x)=x*F(x), where x is the first factor, and F(x) is the limit of the infinite products of the subsequent factors; if we take the derivative (uniform convergence was already justified), we get: f'(x)=F(x)+x*F'(x); therefore f'(0)=F(0) provided that we assume that F'(0) is limited: remind that the f_k(x) are rational functions with both poles and zeroes that are negative integers, except for the factor x, that is absent in F(x). Moreover F(0) is not 0, and thus f'(0) is not 0. d) The application of the D.H. theorem is justified since the uniform convergence grants the continuity of f(x) and f'(x); in fact from the functionsl equation, we get: f(x+1/2)=f(x)/f(2x); by virtue of continuity we can take the limit of both sides as x tends to zero: on the left we immediately obtain f(1/2), whilst on the right side we have the right conditions for the application of the DH rule, since the limits of f(x) and f(2x) are both 0, as x tends to 0, but the limits of their derivatives, i.e. f'(x) and 2f'(x), respectively, are both non zeroes; therefore, whatever is the finite value of f'(x), thr DH rules gets the value 1/2 for such limit ratio. e) from a rigororous theoretical point of view, the most difficult point is the proof of continuity for f'(x), that is necessary for the application of the DH rule; such continuity of f'(x) is not simply implied by the uniform convergence of the f_k sequence, and by the fact that f'_k are continuos: it is necessary to verify that the f'_k sequence is uniformly convergent, too. Then such limit effectively represents f'. To this aim I employed a quite cumbersone demonstration: 1) the f'_k are evaluated from the polar expansions of the f_k functions, that are rational functions, with an equal number of zeroes and poles at negative integer points; as like as f_k, f'_k are continous except at the isolated negative integer "polar" points; 2) the sequence f_k is uniformly convergent, then it is uniformly Cauchy. 3) through a non elementary comparison of mutual differences |f_n -f_m | and |f'_n -f'_m | (using the abovementioned "polar" expansions) for high index values n,m, it is possible to show that also the derivatives sequence f'_k is uniformly Cauchy. 4 ) by virtue of completeness of the functional space the uniform convegence of the f'_k sequence is granted. 5) as a consequence f' is a continuous function
Took me a minute to work out why we've got weird indexes at 3:30; I was thinking of the number as ((1/2)/3)/4 which is really just 1/n! The expression is more ((1/2)/(3/4))/((5/6)/(7/8)) which explains the weird indexes. I should have spotted that sooner, but the writing it with only a slightly longer line to indicate order threw me off.
I had a hunch about 3:37 before you gave the answer! :) When I saw the partitioning into numerator and denominator I thought of the Thue-Morse sequence.
Why would anyone write it that way and I think je made a mistake f of x plus 1 in the denominator is not x plus 2^n it should be x plus 2 TIMES N since otherwise you are forgetting about the even numbers that are not powers of 2..
Pausing the video after the question was stated and trying to work things out on my own, I easily got as far as noting that when the expression is simplified into a product on the numerator and a product on the denominator, where each integer goes is determined the parity of the number of ones in the binary representation of the number you get if you subtract one from that integer. That is the easy part. But I would never have figured out what to do next!
@@edmundwu6507 , thanks for your explanation. I understood the alternation between numerator and demonimator. I have seen where was my mistake. In my mind, we multiply the upper limit of the product (I don't know why). 🤦♂️
The reason lim_{x->0} f(x)=0 is because the numerator of the infinite fraction has an x term. This is the only term which causes the problem. When u differentiate, it. There will be 1 term where this x term vanishes, this will be the only non-zero contribution. A similar logic can be used for f(2x) and f'(2x) at x=0.
from what he writes at around 3:00 you can see that f_m(x) is just the ratio of two polynomials with all negative roots, which shouldn't give us trouble over the positive numbers
Now this was somewhat confusing. First tricky place, at 8:55, Θ(m) is half of the time 1, and half of the time -1, but this is only true for odd m values that we can cancel all the multiplications by two. Which is our case, but still, that took some clarification for me to the very definition of a limit of a sequence to make sure we can put that multiplier of 2 inside. And another one at 10:36 - if both infinite products of (2x+2m+1)^±Θ(m) converge individually (to some t and 1/t) - that's not a problem, but if not, then merging them together - isn't it like multiplying zero, which is a product of halves, and infinity, which is a product of twos, and declaring result one?
And he made a mistake if x equals 1 at 4:00 . X plus 6 should be in the denominator and x plus 7 should be in the numerator..and f sub 3 would only go up to x +4/×+5 so why did he even put the x +6/×+7 term in there..
Is this actually follow able and correct..can't you plug in first few values and see the pattern that way? For example when you get up to 5/6 as the final term the answer is 4/5 ..isn't that the start of a pattern?
after thinking about it for a few seconds i immediately realized the link with the thue-morse sequence, turns out doing some competitive code golfing several years ago has its uses (in solving obscure math problems)
Might this limit also be found by using a recursively-defined inequality? 3/4 > 1/2 ; (5/6) / (7/8) > (1/2) / (3/4), etc. I could see that it wasn't going to climb all the way back up to 1 but was a little surprised that it came out as low as .707+ , because the third term is already .666...
Even if it's smaller than 1 always we haven't shown it doesn't possibly bounce between multiple values, i.e., for some large n f_n(1) = .24, f_n+1(1) = .76, f_n+2(1) = .249, f_n+3(1) = .751, etc.
Omg, beautiful problem. I can follow all those steps, but it really requires some good "guesses" to solve this problem; I would have not been able to do it by myself.
But for fxn plus 1 it isn't x plus 2 raised to the n..it's 2 times nnsince you have all the even numbers that are not pure powers of 2 .did he forget about those?
We introduce a variable x which we know we are later going to set to a constant. It's a trick but it's a valid one and sometimes (like here) it actually gets us somewhere we couldn't have got without the algebraic steps.
It turns out that pi can be expressed as an infinite product of rationals, as illustrated in this video m.ua-cam.com/video/cI6tt9QfRdo/v-deo.html (timestamp 57:31)
I'm probably making some mistake, but I don't see why (the limit at 0 of) f prime of x divided by f prime of 2x is not still another indeterminant form of infinity/infinity?
One thing i notice with this fraction is that if you read the numbers you get the fair share theorem. ABBABAABBAABABBA... where the rule for a fair share sequence of length n is to take the first n values of the infinite sequence which you get by successively copying the entire sequence and appending an inverse copy where you swap every occurrence of A and B
doi.org/10.2307/2321105 www.jstor.org/stable/2321105 These links both need a subscription - try them at a library? arxiv.org/pdf/1709.04104.pdf This one is a generalisation with Thue-Morse sequences, but is free and mentions this problem specifically. Super math heavy though!
I guessed that the sequence was approaching sqrt(1/2) and tried to find the limit of the square of the sequence (1*1*4*4*6*6*7*7*...) / (2*2*3*3*5*5*8*8*...) and cancel out factors, but it didn't go anywhere
Kind of an all over the place video. Could follow it all the way through though, except at the end where you just evaluated the limit. The place to stop wasn't good this time
At first I thought, I would never come up with that binary digit counting function. But I did see the fractal nature of Up, Down, Down, Up, Down, Up, Up, Down, etc.
I love how a little algebra, parity/combinatorics, and analysis led to a result that surprised me. (I've seen irrationals form as infinite sums of rationals, but not as an infinite ratio of them; that seems fitting somehow, irrationality as an infinite ratio of ratios.) I wrote a couple lines of Python to see it happen numerically. Convergence was faster than I expected, too (ten terms/doublings leads to more than that many digits of accuracy) : nums = [i for i in range(1, 1 + 2**10)] while len(nums) > 1: nums = [nums[i] / nums[i + 1] for i in range(0, len(nums), 2)] print(nums[0]) print(1 / 2**.5) : 0.707106781186 0.707106781187
I’d just like to point out that I’m not responsible for this, I was only 9 at the time!
oh my god it's the real D. Woods
Relevance?
@@anshumanagrawal346 "It was a problem that proposed by D. Woods." In the first 10 seconds.
I was -25 years old
Classic D. Woods, so modest
So inverse construction gives yet another definition for √2. Neat!
Cannot be represented easily
@@Xphy When has that ever stopped mathematicians
That was a really interesting problem. It combined some analysis and number theory. I'm going to have to go back over it a couple of times though.
I don't think I quite understand why the f'(x) is fine at 0. As well as some other things.
I think because f(x) was the limit of f_n(x) with x in the numerator so f(0)=0 and the derivative is well behaved because nothing in the denominator will be 0 for x=0
I know this problem. D. Woods is Don Woods. We were office-mates in grad school. He showed me the problem some time later, probably in the 90's. I have considered proposing this problem as a possible video. I hoped it would include the real analysis to show that f(x) is well-defined (ie, that the sequences do converge), continuous (except at poles at some negative integers), and differentiable. I guess my hoped for target audience is undergrads currently taking real analysis.
2:35 I think the point of the denominator being f_n(x+2^n) needs more justification, I see why it is correct since the next denominator term would be x+4, but I think it would be helpful to further include other terms in order to make this solution clearer.
And why And why gods name does he choose f of 2x and f of x plus one half..that's random..nkt justified..and what does he mean f of 1??
@@angelmendez-rivera351 yea if course I saw and knew that but why does he have that one half there?
For others scouring JSTOR: the problem (E2692) was actually proposed in Jan 1978 (Vol. 85, No. 1, p. 48); the solution was published in May 1979.
5:15 I like that little speed up, nice editing
I suggest to read the paper, even if it is a bit laconic. Many details have to be rebuilt.
a) the proof of the convergence is based on a fundamental theorem of product sequences with factors of the form 1+a_n: such product converges iff the series with a_n terms is absolutely convergent; as a matter of fact, the factors of the functions f_k(x) can be associated in quartets, according to the 4-module remaind; with immediate algebra it is easy to rearrange any of this quadruple factor as (1+a_n) with a_n being a o(1/n^2) term as the natural index n tends to infinity; therefore the convergence can be grounded on the basis of the abovementioned general condition for infinite products.
b) it is immediately verified that such convergence is uniform with respect to the x variable; in fact, the terms a_n are functions of x, i.e. let a_n(x), and it can be easily checked that the convergence of the series with a_n(x) terms is uniform ; so the convergence of the infinite product with factors 1+a_n;
c) f(0)=0 because of the first factor of the infinite product i.e. x; any other factors is non-zero for x=0; therefore we can let f(x)=x*F(x), where x is the first factor, and F(x) is the limit of the infinite products of the subsequent factors; if we take the derivative (uniform convergence was already justified), we get:
f'(x)=F(x)+x*F'(x); therefore f'(0)=F(0) provided that we assume that F'(0) is limited: remind that the f_k(x) are rational functions with both poles and zeroes that are negative integers, except for the factor x, that is absent in F(x). Moreover F(0) is not 0, and thus f'(0) is not 0.
d) The application of the D.H. theorem is justified since the uniform convergence grants the continuity of f(x) and f'(x); in fact from the functionsl equation, we get: f(x+1/2)=f(x)/f(2x); by virtue of continuity we can take the limit of both sides as x tends to zero: on the left we immediately obtain f(1/2), whilst on the right side we have the right conditions for the application of the DH rule, since the limits of f(x) and f(2x) are both 0, as x tends to 0, but the limits of their derivatives, i.e. f'(x) and 2f'(x), respectively, are both non zeroes; therefore, whatever is the finite value of f'(x), thr DH rules gets the value 1/2 for such limit ratio.
e) from a rigororous theoretical point of view, the most difficult point is the proof of continuity for f'(x), that is necessary for the application of the DH rule; such continuity of f'(x) is not simply implied by the uniform convergence of the f_k sequence, and by the fact that f'_k are continuos: it is necessary to verify that the f'_k sequence is uniformly convergent, too. Then such limit effectively represents f'. To this aim I employed a quite cumbersone demonstration:
1) the f'_k are evaluated from the polar expansions of the f_k functions, that are rational functions, with an equal number of zeroes and poles at negative integer points; as like as f_k, f'_k are continous except at the isolated negative integer "polar" points;
2) the sequence f_k is uniformly convergent, then it is uniformly Cauchy.
3) through a non elementary comparison of mutual differences |f_n -f_m | and |f'_n -f'_m | (using the abovementioned "polar" expansions) for high index values n,m, it is possible to show that also the derivatives sequence f'_k is uniformly Cauchy.
4 ) by virtue of completeness of the functional space the uniform convegence of the f'_k sequence is granted.
5) as a consequence f' is a continuous function
4:24 Yeah you're right I would have never thought to check different bases. I wonder what are other ways of seeing a pattern there?
Matt Parker has a great video on it: ua-cam.com/video/prh72BLNjIk/v-deo.html
@@mebamme cool, thanks
Took me a minute to work out why we've got weird indexes at 3:30; I was thinking of the number as ((1/2)/3)/4 which is really just 1/n!
The expression is more ((1/2)/(3/4))/((5/6)/(7/8)) which explains the weird indexes. I should have spotted that sooner, but the writing it with only a slightly longer line to indicate order threw me off.
I'm curious, does this function has its name? What properties does it have? Can it be expressed in whatever closed formula form?
At 3:30 I was thinking of the Wallis product
One question, right at the end, how do you know f'(0) is not zero? or why it's even defined?
13:45 how do you know that f'(0) is not zero? This feels very rushed to me.
The only troubling term for f(x), x tends to 0 is for m = 1. However, theta(0) = 1. Hence no problem for f(x) and f'(x), x tends to 0.
I had a hunch about 3:37 before you gave the answer! :) When I saw the partitioning into numerator and denominator I thought of the Thue-Morse sequence.
Why would anyone write it that way and I think je made a mistake f of x plus 1 in the denominator is not x plus 2^n it should be x plus 2 TIMES N since otherwise you are forgetting about the even numbers that are not powers of 2..
Pausing the video after the question was stated and trying to work things out on my own, I easily got as far as noting that when the expression is simplified into a product on the numerator and a product on the denominator, where each integer goes is determined the parity of the number of ones in the binary representation of the number you get if you subtract one from that integer. That is the easy part. But I would never have figured out what to do next!
2^n is not obvious with only those 3 iteration
It’s pretty obvious you double the amount of numbers in each iteration, 2^n is only logical.
9:18, I don't understand why we can multiply by 2.
11:30, the first line is wrong. f(x+1/2) = f(x)/f(2x).
we're multiplying by 1, which is 2/2, and since half of the terms are on the numerator, half on the denominator, he did what he did
@@edmundwu6507 , thanks for your explanation. I understood the alternation between numerator and demonimator. I have seen where was my mistake. In my mind, we multiply the upper limit of the product (I don't know why). 🤦♂️
How are we sure that f' exists and that f'(0) is not zero?
The reason lim_{x->0} f(x)=0 is because the numerator of the infinite fraction has an x term. This is the only term which causes the problem. When u differentiate, it. There will be 1 term where this x term vanishes, this will be the only non-zero contribution. A similar logic can be used for f(2x) and f'(2x) at x=0.
2:13 quite a leap without extending out at least one more term
2 tikes one half equals 1 and so is 1/2 plus 1/2 so it should be f(1) not f(1/2) at 12:50
We can assume the function is both continuous and differentiable?
from what he writes at around 3:00 you can see that f_m(x) is just the ratio of two polynomials with all negative roots, which shouldn't give us trouble over the positive numbers
All the functions used are products of continuous functions. Not to mention, all rational functions are continuous in their domain of definition
I didn't quite understand how you are sure that the derivative exists and it's well defined at 0
Maybe the convergence is uniform
Wow such a simple problem got us through so much trouble I'm ... I'm baffled!
Now this was somewhat confusing.
First tricky place, at 8:55, Θ(m) is half of the time 1, and half of the time -1, but this is only true for odd m values that we can cancel all the multiplications by two. Which is our case, but still, that took some clarification for me to the very definition of a limit of a sequence to make sure we can put that multiplier of 2 inside.
And another one at 10:36 - if both infinite products of (2x+2m+1)^±Θ(m) converge individually (to some t and 1/t) - that's not a problem, but if not, then merging them together - isn't it like multiplying zero, which is a product of halves, and infinity, which is a product of twos, and declaring result one?
And he made a mistake if x equals 1 at 4:00 . X plus 6 should be in the denominator and x plus 7 should be in the numerator..and f sub 3 would only go up to x +4/×+5 so why did he even put the x +6/×+7 term in there..
And why do that dirty trick with the half and squaringit..no one is going to think of that..solve it without dirty tricks please..
small typo in the title: 'Montly'
im gonna need to watch this one a couple times
Is this actually follow able and correct..can't you plug in first few values and see the pattern that way? For example when you get up to 5/6 as the final term the answer is 4/5 ..isn't that the start of a pattern?
after thinking about it for a few seconds i immediately realized the link with the thue-morse sequence, turns out doing some competitive code golfing several years ago has its uses (in solving obscure math problems)
Might this limit also be found by using a recursively-defined inequality? 3/4 > 1/2 ; (5/6) / (7/8) > (1/2) / (3/4), etc. I could see that it wasn't going to climb all the way back up to 1 but was a little surprised that it came out as low as .707+ , because the third term is already .666...
Even if it's smaller than 1 always we haven't shown it doesn't possibly bounce between multiple values, i.e., for some large n f_n(1) = .24, f_n+1(1) = .76, f_n+2(1) = .249, f_n+3(1) = .751, etc.
Why should the function f(x) be continous and derivable?
Omg, beautiful problem. I can follow all those steps, but it really requires some good "guesses" to solve this problem; I would have not been able to do it by myself.
But for fxn plus 1 it isn't x plus 2 raised to the n..it's 2 times nnsince you have all the even numbers that are not pure powers of 2
.did he forget about those?
Always surprising that a product (or quotient) of rational numbers is irrational.
I was surprised that it's algebraic. The Thue-Morse constant is transcendental.
1:00 You say 9 over 10, 10 over 11. I think you meant 9 over 10, 11 over 12.
Yeah, it wasn't written in front of him, so he screwed it up, & that's where I stopped the video. *_Phooey!_*
I'll admit I didn't manage to do this one in my head.
How is it possible to use the algebraic approach when there's no x in the expressions??
We introduce a variable x which we know we are later going to set to a constant.
It's a trick but it's a valid one and sometimes (like here) it actually gets us somewhere we couldn't have got without the algebraic steps.
@@trueriver1950 thank you
Thank you very much professor for a very cool problem! This leads me to wonder what other infinite products of rationals give irrational numbers.
It turns out that pi can be expressed as an infinite product of rationals, as illustrated in this video m.ua-cam.com/video/cI6tt9QfRdo/v-deo.html (timestamp 57:31)
I'm probably making some mistake, but I don't see why (the limit at 0 of) f prime of x divided by f prime of 2x is not still another indeterminant form of infinity/infinity?
The function has in the numerator: x so by differentiating you remove that in one of the term of the infinite sums so you don’t get 0
@@swelters29 I agree you don't get zero, but why don't you get infinity?
@@Alex_Deam Because none of the denominators are 0 when x = 0 and x is in the numerator.
As someone from Albany NY it’s funny to see him wearing a sweatshirt from the NY state museum 😂
One thing i notice with this fraction is that if you read the numbers you get the fair share theorem. ABBABAABBAABABBA... where the rule for a fair share sequence of length n is to take the first n values of the infinite sequence which you get by successively copying the entire sequence and appending an inverse copy where you swap every occurrence of A and B
The fair share theorem, of course, being a theorem for deciding when in a ranked order of choosing events each party is allowed to make a choice
I'm struggling with how to simplify the big multilayered fractions into the simplified forms that you have. 😅
Hi Micheal. Can you please provide links in the description to the problem's statement and solution?
doi.org/10.2307/2321105
www.jstor.org/stable/2321105
These links both need a subscription - try them at a library?
arxiv.org/pdf/1709.04104.pdf
This one is a generalisation with Thue-Morse sequences, but is free and mentions this problem specifically. Super math heavy though!
13:59
a great problem, was not easy to follow though as there were some short cuts.
Correction : m = 0
I guessed that the sequence was approaching sqrt(1/2) and tried to find the limit of the square of the sequence (1*1*4*4*6*6*7*7*...) / (2*2*3*3*5*5*8*8*...) and cancel out factors, but it didn't go anywhere
Where did he get that formula at 3:00 the fn2 is x pkus 2^n isn't clear at first?
Kind of an all over the place video. Could follow it all the way through though, except at the end where you just evaluated the limit. The place to stop wasn't good this time
“We have the same dreams … or is it the same nightmare”
-Akon and Jeezy
It is so cute!
At first I thought, I would never come up with that binary digit counting function. But I did see the fractal nature of Up, Down, Down, Up, Down, Up, Up, Down, etc.
Robin Wood :-)
OOF! All it took was_*ONE NOT-WRITTEN FRACTION_ --
*& YOU! BLEW! IT!*
Verified by mathematica
and that's a good place to sto
Nice
That was a really cool problem and a very nice solution! I can only wonder what would happen with a different sequence for the fractions...
Like the Fibonnaci sequence?
That was the first thing that came to mind.
I love how a little algebra, parity/combinatorics, and analysis led to a result that surprised me. (I've seen irrationals form as infinite sums of rationals, but not as an infinite ratio of them; that seems fitting somehow, irrationality as an infinite ratio of ratios.) I wrote a couple lines of Python to see it happen numerically. Convergence was faster than I expected, too (ten terms/doublings leads to more than that many digits of accuracy)
:
nums = [i for i in range(1, 1 + 2**10)]
while len(nums) > 1:
nums = [nums[i] / nums[i + 1] for i in range(0, len(nums), 2)]
print(nums[0])
print(1 / 2**.5)
:
0.707106781186
0.707106781187