Well i guess we immediately know that linear functions are part of the solutions, but do we know for sure there are no other solutions? I guess that's the tricky part :)
Yes, exactly the same happened to me. I was like: Clearly is a linear function and it's easy to show that a linear function is a solution, now show that it's the only one.
Once we got to f’(x) = c, we have already proven that all linear functions satisfy the equation. If we integrated f’(x) = c with respect to x, we will get: f(x) = cx + k, which is the general equation for all linear equations.
@@PythonPlusPlus Technically we've only proved that linear functions satisfy the equation for n = 1 and n = 2. I think we need one more step to show that any linear function satisfies the equation for all n which is straightforwards by plugging f(x) = cx + k, f'(x) = c into the original equation and simplifying.
@@OMGclueless this equation is the same as saying when does the tangent equal the secant line right since what we have in the right hand side of the equation is in fact the average rate of change as x goes from x to x plus n..
Hello, I remember a Russian professor I had years ago mentioning a question quite similar to this one being asked in oral exams during the Soviet times. The answer of course, was rather simple based on intuition, but it was explaining it to your interlocutor which would have been the more difficult part.
Strictly speaking: The proof is incomplete. At the end of the video it is shown that linear functions are the only possible solutions. The easy part of verifying that indeed all of them are solutions is missing.
Thank you, I was thinking that what he did was demonstrate that only lines can possibly satisfy the equation for all n, since only lines do for n=1,2. And like you said, it's really easy to verify that any line c*x+d does indeed satisfy the equation.
So the question is - which function has its mean value in the interval [x,x+n] equal to its derivative at x, for all real x and integer n. So by the mean value theorem, there's a c in [x,x+n] with f'(c)=f'(x), for all x. Since we can shift x by any real value, the only possibility is f'(x) = constant for all x. That is, f(x) = ax+b.
@@maxime_weill LHS is the slope at x, RHS is the average slope in [x,x+n]. If they're equal in general, by the mean value theorem, the function can not be either concave or convex anywhere. So it must be linear everywhere.
Very simple! The question is saying that: What is the function where the slope at a specific point (derivative) is exactly equal at all times to the slope of the line that connects between the same point and another point in the function? Of course the only function that satisfies this condition is the linear function. A curved function would never satisfy the condition because the line that connects two different points in the function would intersect the function and its slope would never be the same as the slope of one point of them.
@@maxime_weill Actually for "n" being a natural number is just a special case from the general case where "n" is a real number, but in anyway that wouldn't change anything.
@M Sami But you're making the question look easier than it is. You're saying the question is stating that the slope at a point x is equal to the slope of any chords ( line going throught 2 points of the graph). And that's wrong.
@Sthaman Sinha It's not that simple. The integer restriction makes things more complicated. For example f(x) = {x if x mod 1 < 0.5, -x if x mod 1 >= 0.5} satisfies the equation, except that it's not differentiable. n being a natural number *does* matter because in theory there can be more solutions when n is a natural number than when n is a real number and the question asks for *all* solutions. Somehow your proof must show that all these other solutions are non-differentiable.
You can also show f''(x) = 0 everywhere: It is easy to show that a) f' is again differentiable b) The second derivative is f''(x) = f'(x+1) - f'(x) = f(x+2) - 2f(x+1) + f(x) c) f(x+2) = f(x) + 2f'(x) = f(x) + 2(f(x+1) - f(x)) Combining these shows f''(x) = 0.
We can also solve it this way : Let a,n € N Consider nf'(x+a) = f((x+a)+n) - f(x+a) --- (1) Also for any integer a+n (a+n)f'(x) = f(x+(a+n)) - f(x) ---(2) (2) - (1) yields : (a+n)f'(x) - nf'(x+a) = f(x+a) - f(x) as a is a natural number, the RHS is equal to af'(x). Thus, (a+n)f'(x) - nf'(x+a) = af'(x) And it follows that nf'(x) = nf'(x+a) for all natural n. As 0 is not a natural number, we can divide both sides by n, concluding that : f'(x+a) = f'(x) for any integer a. I.e d/dx( f(x+a) - f(x) ) = 0 Thus, f(x+a) - f(x) = c for all naturals a. Using the initial functional equation, we conclude f'(x) = K and thus f(x) = Kx+C. Edit : I realised that I did basically the same thing as in the video. Nvm.
Thanks! Maybee more elegant would be to use Fundamental Calculus Theorem for f’(x) on x...x+n then mean value theorem to prove that f’(x) is a constant.
I feel like this was a really simple problem. It is just the definition of a derivative without the limit. So for any x, all points (x+N, f(x+N)) must be collinear. Already intuitively it must be a line. Suppose f'(x+c) != f'(x) for 0 < c < 1, then |f(x+c+k) - f(x+k)| ->infty for k in N, k->infty, so the function cannot be smooth
This is how i tried to do it, but I found it tricky to prove the function had to be smooth. It does, because " f' = linear combination of f " with f differentiable implies f is smooth.
Could you be so nice to do something involving a consistency check for a Runge-Kutta method? For example, I can't really wrap my head around this task, but it does not have to be explicitely this. Anything similar should work. Consider the Runge method 0 | 0 0 1/2a | 1/2a 0 --------------------------- | (1-a) a and determine whether it is consistent or not. Also check if there exists values for a such that the method is consistent of order 3 despite it's tableau size.
Great work. Of course the intuitive answer can be argued as such: the instantenoues rate of change is identically equal to the average rate of change only for linear (and constant) functions, for all x in the domain of f(x).
@@axemenace6637 Bruh he wasn't trying to prove it. He was saying that you can think of it like this before doing a proof to kinda get an intuition for what the answer should be
You know....... When you look back at the problem it makes perfect sense, because the first order finite difference schemes approximates the derivative f'(x) assuming that f(x) is a first order polynomial. That's more or less the setup of this problem is, except n is a natural number not all non zero real number, I'm guessing It should be possible to extend this to finite differences of higher orders, so for example all the solutions to the DE f'(x) = (f(x+n)-f(x-n))/2n should be all polynomials of order 2.
It's easy to see in the beginning that all linear functions satisfy the rule. But to prove that no more functions satisfy the rule is the more challenging part.
the proof was cool but the Intuition is quite simple: since n is not approaching zero, it wont be the instantaneous rate of change unless f(x) is straight and not curved. So f(x) must be linear.
I solved this through the use of Taylor's Theorem. We saw that f'(x) = [f(x+n)-f(x)]/n This implies that nf'(x) = f(x+n) - f(x) so long as n !=0 (there is some convention about 0 being a natural number, but we'll discount that). Rearranging, we have f(x+n) = f(x) + nf'(x) We can similarly Taylor Expand f(x+n) with respect to the variable n, with n_0 = 0 [a Maclaurin Series]. Also note that the derivative of f(x+n) with respect to x and with respect to n are the same. By this, we have f(x+n) = f(x)+nf'(x+n) + (1/2)n^2f''(x) + O(n^3) Comparing the two results we have found, we see that (1/2)n^2f''(x) + O(n^3) = 0 Since we are looking for functions that satisfy this for all n, we are left with f''(x) = 0. Note that this second derivative condition is the strongest condition we get. Having the second derivative being zero immediately implies that all the higher order derivatives are 0. This immediately implies that f(x) = a+bx for real numbers a,b Observe the following: f'(x) = b [f(x+n)-f(x)]/n = [a+b(x+n) - (a+bx)]/n = bn /n = b Thus our postulate is satisfied by these functions a+bx From our initial derivative condition, we showed that the functions must be linear, moreover, every linear function satisfies this condition. Also note that this was only done with the assumption that n!= 0, and nowhere did we assume that n was a natural number. Indeed, this proves something even stronger in that we can pick n to be any nonzero real number.
This is far from being a proof 1) the exercise asked for all differentiabile function, NOT 2 times differentiabile function 2) if you consider n to be continuous (and you used it in order to say that f"(x)=0 ) you are asking for function which satisfy a much more strict condition, so nobody tells you that there is some nonlinear function which do not satisfy the identity required for all n in R, but still, satisfies it for n in N Example: if I ask for (differentiabile) functions which satisfy f(x+n)=f(x) for all x in R and for all n in R you end up with f being a constant; if you want that equality being satisfied for n in N you have much more functions, all function having period 1 (it isan infinity dimensional vector space of function).
@@mario_veca You do know that it is twice differentiable.. Since the derivative is a linear combination of differentiable functions f(x+n) and f(x), the derivative is differentiable. You can then use induction to show that it is infinitely differentiable. However you do not know that the Taylor series is convergent, so you may not be able to expand ina Taylor series.
I'm not that familiar with the Putnam exam. It seemed obvious to me at the beginning that the solution was any linear or constant function. On the exam, would it be necessary to provide a rigorous proof like this one, or would it be sufficient to simply state that in order to meet the conditions presented, the function must have a constant rate of change?
I feel like whenever one answer is linear functions it ends up being the only answer. Im just conjecturing here but is there some kind of uniqueness theorem for functional equations when one solution is a linear function?
A beautiful way to do this is as follow :Since f' is a linear combination of differentiable function, f is twice differentiable. Take the initial equation and instead of f'(x)=1/n(f(x+n)-f(x)) write f'(x+n)=1/n(f(x+2n)-f(x+n)) then replace f'(x+n) with nf"(x)+f'(x) and f(x+2n) with 2nf'(x)+f(x) and finally f(x+n) with nf'(x)+f(x) thus you will get f"(x)=0, it's easy to go on from this.
@@MichaelPennMath f'(c)=(f(b)-f(a))/(b-a) for a continuous and derivative function, being c a point in the interval (a, b). Making b=x÷n and a=x, then f'(c)=f'(x) and f"(c) is a constant value u. Then integration. f(x) = ux + v. Thank you
I done this by other way: if x=0: f'(0)=(f(n)-f(0))/n f'(0)=tan(theta) (f(n)-f(0))/n=tan(alpha) So theta=alpha Because theta is constant, alpha is constant too, so because alpha is constant f(x) is a straight line, so it's of the form ax+b
if you know that constant func derivative is zero and only if it is constant, then it is easy to prove that if two functions have the same derivative, then their difference must be constant. (he did it in the video) At last, if you dy/dx linear you will have a constant. So if you have df/dx = A, then f = Ax + C
well there is a much easier and more intuitive way to solve this. the "discrete version" of the differential quotient defined in the question is simply a secant of the curve, meanwhile its limit is the tangent of the curve. knowing this we can conclude and even prove that the set of linear functions is the only solution. because we can approach the same question from a different, but equivalent way: which functions are those whose tangent's slope at any given point is equal to the slope of an infinite number of other secants drawn from the same point? the line is the only geometrical structure which satisfies this since the line is the only geometrical object in which case the tangents are identical to the secants (so the tangents and the secants degenerate into the same object).
A purpose of the derivative is to linearize and it becomes more accurate on a function with h -> 0 for the formal def. The only class of functions that dont care about this limiting behavior is already linearized functions themselves. Is this sound reasoning?
Wat? Surely any function at all of the natural numbers has a derivative, provided theres no infinite values. I mean, x^2 has a derivative in the reals, right? Why doesnt it have a derivative over the rationals?
@@MichaelPennMath Oh ! Yes. It is on my sheet but I forgot to write it in my comment. But nothing changes : f'(x)=a+2𝜋sin(2𝜋x)=a+2𝜋sin(2𝜋x+2𝜋n)=f'(x+n)
You do have f'(x)=f'(x+n) here so f(x+n)-f(x) is a constant but that's all you get. In the exercise you need to assume that f verifies the original equation to get f'(x)=C.
I approached it with a method that is bit more mathematically sophisticated and systematic. I observe that if h(x) and g(x) are solutions then all linear combinations, Af(x)+Bg(x), are solutions. A little play indicates that Ax+B is a solution. So I can write f(x)=g(x)+f''(0)x+f(0). Where g(x) is also a solution but with g'(0)=0 and g(0)=0. Then write $g(x)=\int p(k)e^(ikx) dk $. Plug that in and you discover that p(k) =0 when k!= 0. So g(x) is at most a constant and thus 0.
The fact that f satisfies the equation for all n is the assumption. He only needed to write it for n = 1 and 2 because it gave enough necessary conditions to narrow down the solution f. After proving that f is necessary an affine function, he should have proved that affine functions satisfy the equation but it's quite simple.
Could you also have trigonometric functions (with period of 1) that 'look' linear from far? I mean like x + sin(x) or cos(x) - x or something. Would that even be possible?
Yeah, the proof is incomplete as is. To fix it, you would need to use the same process but instead of substituting 1 and 2 as n, use n and 2n. If you work it out, you will get f’(x)=f’(x+n) and this will narrow the solution to only linear functions. I hope this helps!
I agree that this would be a more elementary proof if Michael showed that the property was satisfied by all affine functions (which is what he means when he says "linear functions"). But I don't agree that it's incomplete as he presents it. He's appealing to previous results: you can prove using the Mean Value Theorem that the only continuous functions that have derivative identically 0 are constant--and then you can cite that result any time you want without proving it again. Similarly, the Mean Value Theorem implies that the only continuous functions that have constant derivative are affine functions. And then you can cite that result any time you want without having to prove it again. This is what he means when he says "by elementary differential calculus." Also, for the people thinking about periodic functions with period 1: it's true that those functions will satisfy the property f(x+1)-f(x)=0, but it is not true that they satisfy the original property from the statement of the problem. Such functions will have f(x+n)-f(x)=0 for all x and for all n, but they will not have f'(x)=0 for all x (otherwise, they would be constant functions...because Mean Value Theorem). This is exactly the point that No Way Haze makes below: Michael shows that, if a function satisfies Property A, then it also satisfies Property B; that doesn't mean that any function satisfying Property B also satisfies Property A.
So in this proof you essentially only used the fact f'(x) = f(x+1)-f(x) = (f(x+2)-f(x))/2 and didn't need the statement for higher n. But what if we only assume f'(x) = f(x+1)-f(x) ? In other words, is there a differentiable function f: R -> R that satisfies f'(x) = f(x+1) - f(x) but is not linear? I guess that at least for infinitely differentable functions there shouldn't be any, but I couln't prove it yet.
the tangent line must intersect all a+n, if its not tangent to some a+n then a+n+1 intersects two different tangent lines which is impossible, so f' is periodic with period 1 so d/dx(f(x+1)-f(x))=0 so f(x+1)-f(x)=C, f(x+1)-f(x)/1 = f'(x) so f'=C and f(x)=Cx+D
Is this proof wrong: I saw that the right side of the original equation was the limit def. of a derivative so I recognized that it must be the average rate of change over an interval of [x, n]. Assuming there is a function whose derivative at one point is the same as its average rate of change from one point to another arbitrary point exists, this implies that any change in the second point won't cause the original equality to become false. A function that does this must have the same derivative everywhere because if not, then changing the second point will make the original equality false. The only function whose derivative is constant every where is a linear function f(x) = mx + b. I thought it might be wrong because I didn't use the fact that n (which I referred to as the 'second point') is element of the natural numbers, even though that isn't necessary for my explanation.
@@tonymontana9221 ok thanks but why couldn't say n=3 and n=4 produce different additional properties giving a more general solution for f'(x). I strongly suspect they don't but I thought he would do an induction step or something to show this and only this solution for all n. Apologies if I'm not getting this
@@markkennedy9767 The hypothesis say that for every n, the function f must satisfy a given property. Using the cases n=1 and n=2, he derives a NECESSARY condition that all solutions must satisfy, namely that they are straight lines. Then he says he is done, but he should have checked that, in fact, all straight lines satisfy the hypothesis, which means that being a straight line is a SUFFICIENT condition, hence proving that the functions that satisfy the hypothesis are, precisely, the straight lines. This means that the solution to this problem is exactly the same as the solution to the problem relaxing the condition "for all n" to only "for n=1 and n=2".
It is incorrect that linear functions are the only solutions. Namely, this system is linear time invariant for which in general the solutions are often of the form exp(a x). Plugging that into the initial differential equation yields a=(-W_k(-1/e)-1)/n, with W_k(x) the kth Lambert-W function. It can be noted that for k=-m and k=m+1 yields complex conjugate values (with positive real part), which means that f(x) could also be a linear combination of exponentially growing oscillations.
At 4:11 you could have just set it equal to a constant rather than your whole random ramble, and in general although this is a nice proof, I think there are much simpler ways to do this
I think I have a simpler solution. If f(x+n) grows to infinity then make n go to infinity in f’(x)=(f(x+n)-f(x))/n and apply l’Hospital with n as the variable and get f’(x)=f’(x+inf)=f’(inf). It follows that f’(inf) exists and is finite and as this is true for all x it follows that f’(x) is constant. Therefore f(x) is a linear function. If f(x+n) does not go to infinity then it is either bounded or oscilates between +/- infinity or infinity and some finite values. If it is bounded then as n->inf we get f’(x)=0 which means f is constant which is a particular case of linear equation. It is easy to show it cannot oscilate as if it oscilates then f’(x) must be 0 for the equation to hold for all n, which is a contradiction. Qed
When we are looking just at the right hand side of the board at the end of the video so what about f'(x)=sin(2*pi*x), which also satisfies f'(x+1)-f'(x)=0 while not being constant. Of course we won't get a valid solution for the problem with this f'(x) so the proof on the right side is not flawless.
No, the proof is fine. In the last line he used the problem hypothesis that f(x + 1) - f(x) = f'(x), combined with f(x + 1) - f(x) = c (which 1-periodic funcions would indeed satisfy) to get f'(x) = c (which they would not).
He was talking about the function g, where g'(x) = f'(x+1) - f'(x), and not f. Since g'(x) = 0, then g(x) = c. That's why f(x+1) - f(x) is constant. What he wrote on the third line would still be satisfied with the function you gave; f'(x) = sin(2πx), where f(x+1) - f(x) = -1/(2π) cos(2πx + 2π) +1/(2π) cos(2πx) = 0, which is a constant in R. The proof is complete.
I made a stupid infinite matrix equation for a vector of all the coefficients of a Taylor series from the x^2 term. And i found all of them have to be zero. So I'm left with the x^1 x^0 terms. It was overly complicated, the way i went about it.
Unnecessarily hard solution: let P(x,n) be the assertion of the problem. Then P(x,n+1) compared with P(x+1,n) and then sending n to infinity implies f’(x+1)=f’(x). Notice that then f’ is periodic, and hence since P(x,n) holds, f’ is bounded (as f is continuous). Then we use the fundamental theorem of calculus: f(x)-f(0) is the integral from 0 to x of f’(t). But this equals floor(x) times integral f’(t), plus a bounded term. Dividing by x and sending x to infinity, we conclude that lim f(x)/x exists (and equals integral f’(t) from 0 to 1). Now we just take n to infinity in our original equation. The RHS converges to a limit L independent of x, while the left is simply f’(x). Hence f’ constant, and f is affine. Notice that this shows we only need the property to hold for sufficiently large n.
And a quick verification shows... f(x)=cx+d; f(x+n)=c(x+n)+d; f'(x)= [f(x+n)-f(x)]/n = (cx+cn+d-cx-d)/ n = cn/n = c (QED) A consequence of this is that the derivative of any smooth continuous LINEAR function does NOT depend on N (i.e "dx" (or delta x)), so we dont even need to think of it as a LIMIT tending to 0. The only time we need to think of it as a limit tending to 0 is for degree 2 or higher. (Quadratic, Cubic etc, as there it DOES depend on N). :) Q: Would it work for f(x) = |x| ?? Strictly speaking no as mod x is not smooth it has a sharp point at 0 where is not differentiable, so we would have to include a domain of validity e.g x > 0 or x < 0 for it to make sense... (it is "piecewise" continuous though but not smooth)
I'm a little bit concerned about the last part of the proof, maybe you could elaborate it a bit more. You say, that from f'(x+1)-f'(x)=0 follows d/dx(f(x+1)-f(x))=0, so the difference must be constant, which of course is correct. But consider the counterexample for c=0: f(x) =sin(2pi*x) f'(x+1) - f(x)'=2pi*(cos(2pi*x+2pi) - cos(2pi*x)) = 0 The condition f'(x+1) - f'(x) = 0 just means that the derivative of the function is periodic. So you would have to rule out all of the non linear but periodic functions in order to complete the proof.
He does. After concluding that f(x+1)-f(x) is a constant, he goes back to the equation f'(x) = f(x+1) - f(x) and replaces the right hand side with said constant.
@@markryback3797 The initial equation satisfied by f is that (for n = 1) f'(x) = f(x+1)-f(x) He proves that f(x+1)-f(x) is constant, therefore f'(x) is constant
for me i found that f" is defined since f'(x)=f(x+1)-f(x) and f"(x)=f'(x+1)-f'(x) then i worked with f'(x+1) since f'(x)=f(x+1)-f(x) we get f'(x+1)=f(x+2)-f(x+1).....(1) since 2f'(x)=f(x+2)-f(x) we have 2f'(x)+f(x)=f(x+2) .....(2) since f'(x)=f(x+1)-f(x) we have f'(x)+f(x)=f(x+1)....(3) using (2) and (3) in (1) we get f"(x)=0 hence f(x)=ax+b but notice that what we have done is true just for n=1 and n=2 and we need to check that this holds true for all n in IN we have nf'(x) =na and f(x+n)-f(x)=a(x+n)+b-ax-b=na hence the solutions of the problem are under the form f(x)=ax+b
Thank you for the solution. It looks so obvious. However, I am still confused how f(x) = cos 2πx agrees to f'(x) = f'(x+1), but it does not solve the initial equation.
same. that's where i got lost (and still am). a function where the slope is the same as the slope at x+1 made me think of trig function. how is it that an answer to the intermediary step is not an answer to the original problem... i'm confused.
So where is the confusion exactly? Trig functions may satisfy f'(x+1) = f'(x) but as you pointed out, we got further restrictions The step at 5:09 is the 'neck breaker' for the trigs
I think the prove is incomplete because d/dx(f(x+1)-f(x)) = 0 *CAN’T* get you a linear function. A sin function with period 1 also satisfies that. I come up with a very different approach. The right part of the equation can’t be written in a integral of f’(x)/n from x to x+n. Let’s randomly pick some x, say 1. The left part is an integral of f’(1)/n from 1 to 1+n, and the right side can be written as f’(x)/n from 1 to 1+n. So we know that f’(x) = f’(1), which is some constant. Therefore, the function must be linear.
The right part of the equation can’t be written in a integral of f’(x)/n from x to x+n. Let’s randomly pick some x, say 1 The left part is an integral of f’(1)/n from 1 to 1+n" What does this mean ? You can write (f(x+n)-f(x))/n as integral(f(t)/n, for t = x to x+n) indeed (I think the assumptions on f are sufficient) Then you can change x if you want, if you put x = 1, you get integral(f(t)/n, for t = 1 to 1+n) You can't assign a value to the variable t inside the integral
His proof is valid, you just skipped some steps. The function f(x+1)-f(x) definitely has to be constant. Your sine finction satisfies this. But it does not satisfy f'(x) = f(x+1) - f(x), which he used in the next step to get f' is constant
I was thinking more in terms of taylor series of f(x+n), but that assumes infinite differentiability :( Then I pondered that f(x) = [x]*f'(x-[x]) + f(x-[x]) --- (1) So, this becomes the study of a real valued function f in the domain [0,1). It's easy to deduce that f'(0) = f(1) - f(0) Let's assume that for some 0 < h < 1, f'(h) f(1) - f(0) (used to denote not equals sign) This would mean that f(1+h) f(h) + f(1) - f(0) But from (1) f(1+h) = f(1) - f(0) + f(h), which leads to a contradiction. This means that for all 0
Would write this as f(x+n) = f(x) + nf'(x). Now this is clearly a line when n can take any value, but only naturals are given. Now observe f'(x+1) = f'(x) + 1f"(x) and (f(x+1+n) - f(x+1))/n = f'(x). By task request, both LHS have to be equal and thus f"(x) = 0, so f has the form f(x) = ax + b (integrate twice). It is easy to show any values for a and b will do. Now how to come up with this? I initially let f(x) be anything, say g(x) between 0 and 1 and reconstructed the rest of f from the (rearranged) task equation. this gives you f(x) = g(x - z) + zg'(x - z) where z=floor(x). Now the task gave us an equation so I computed the LHS and the RHS of that equation. This gives you g"(x - z) = 0 and f"(x) = g"(x - z) = 0. Now g is essentially just f restricted to 0..1 so the whole argument can be done with f itself instead of g. Also n occurs twice in different roles but we can choose a simple value like 1 in one occasion. Actually could even have done that for both n, but it seemed more obvious to let one n just stay.
WTF? I saw the answer right away by looking at the statement. I immediately noticed it was linear functions only, because I am a genius, would that be a valid answer?
It's one of those questions where you immediately know the answer but you have to come up with a way to prove it. Great video!
Well i guess we immediately know that linear functions are part of the solutions, but do we know for sure there are no other solutions? I guess that's the tricky part :)
lol exacty. linear functions were the first thing that came to my mind after reading the problem.
You do? I didn't. Still a good video.
You do? I didn't. Still a good video.
Yes, exactly the same happened to me. I was like: Clearly is a linear function and it's easy to show that a linear function is a solution, now show that it's the only one.
Technically, we should also check that all the linear functions satisfy the equation, since not all of the transformations are reversible here.
I work the other way around, first show that a linear function (any) satisfy the question, then show that only a linear function will do.
Once we got to f’(x) = c, we have already proven that all linear functions satisfy the equation. If we integrated f’(x) = c with respect to x, we will get: f(x) = cx + k, which is the general equation for all linear equations.
@@PythonPlusPlus Technically we've only proved that linear functions satisfy the equation for n = 1 and n = 2. I think we need one more step to show that any linear function satisfies the equation for all n which is straightforwards by plugging f(x) = cx + k, f'(x) = c into the original equation and simplifying.
@@OMGclueless this equation is the same as saying when does the tangent equal the secant line right since what we have in the right hand side of the equation is in fact the average rate of change as x goes from x to x plus n..
@@leif1075 that's what I thought :)) I think u can do this in 4 lines using mean value theorem
It has been awhile since I got my degree in math and I really, really enjoy your videos and it has helped me refresh my love for mathematics.
Hello, I remember a Russian professor I had years ago mentioning a question quite similar to this one being asked in oral exams during the Soviet times. The answer of course, was rather simple based on intuition, but it was explaining it to your interlocutor which would have been the more difficult part.
Right!, nothing like two interlocutors who demand precision and clarity in their dialogue.
Strictly speaking: The proof is incomplete. At the end of the video it is shown that linear functions are the only possible solutions. The easy part of verifying that indeed all of them are solutions is missing.
Exactly.
Thank you, I was thinking that what he did was demonstrate that only lines can possibly satisfy the equation for all n, since only lines do for n=1,2. And like you said, it's really easy to verify that any line c*x+d does indeed satisfy the equation.
Lol 9/10 for Michael 😂
With my luck, if submitted this incomplete proof, I'd get a 2/10. :/
@@ThaSingularity how do you verify that then?
Should've seen that solution coming... Really nice exposition.
This is easier than any putnam problem I've ever seen...
No fancy squares or what have you, just “alright we’re done”
I find these solutions extremely satisfying for some reason
I remember this is one of the first MP videos I saw, and it got me into competition problems. I just did the 2023 Putnam, and it was great.
So the question is - which function has its mean value in the interval [x,x+n] equal to its derivative at x, for all real x and integer n. So by the mean value theorem, there's a c in [x,x+n] with f'(c)=f'(x), for all x. Since we can shift x by any real value, the only possibility is f'(x) = constant for all x. That is, f(x) = ax+b.
Can you explain? I dont understand how you get f' constant
@@maxime_weill LHS is the slope at x, RHS is the average slope in [x,x+n]. If they're equal in general, by the mean value theorem, the function can not be either concave or convex anywhere. So it must be linear everywhere.
This is an interesting approach.
@@sabyasachinayak24 This is a non siquitor and thus false. How do you derive the non-concavity and non-convexity from the mean value theorem?
Very simple! The question is saying that: What is the function where the slope at a specific point (derivative) is exactly equal at all times to the slope of the line that connects between the same point and another point in the function? Of course the only function that satisfies this condition is the linear function. A curved function would never satisfy the condition because the line that connects two different points in the function would intersect the function and its slope would never be the same as the slope of one point of them.
You didn't take into account that n is a natural number.
@@maxime_weill
Actually for "n" being a natural number is just a special case from the general case where "n" is a real number, but in anyway that wouldn't change anything.
@M Sami But you're making the question look easier than it is. You're saying the question is stating that the slope at a point x is equal to the slope of any chords ( line going throught 2 points of the graph). And that's wrong.
@Sthaman Sinha
Exactly!
@Sthaman Sinha It's not that simple. The integer restriction makes things more complicated. For example f(x) = {x if x mod 1 < 0.5, -x if x mod 1 >= 0.5} satisfies the equation, except that it's not differentiable. n being a natural number *does* matter because in theory there can be more solutions when n is a natural number than when n is a real number and the question asks for *all* solutions. Somehow your proof must show that all these other solutions are non-differentiable.
This channel deserve more and more subscribers!!
These problems are saving my month
I conjectured the correct solution at the beginning, but I had no thoughts on how to prove it. Your method makes sense, thank you!
You can also show f''(x) = 0 everywhere:
It is easy to show that
a) f' is again differentiable
b) The second derivative is f''(x) = f'(x+1) - f'(x) = f(x+2) - 2f(x+1) + f(x)
c) f(x+2) = f(x) + 2f'(x) = f(x) + 2(f(x+1) - f(x))
Combining these shows f''(x) = 0.
We can also solve it this way :
Let a,n € N
Consider
nf'(x+a) = f((x+a)+n) - f(x+a) --- (1)
Also for any integer a+n
(a+n)f'(x) = f(x+(a+n)) - f(x) ---(2)
(2) - (1) yields :
(a+n)f'(x) - nf'(x+a) = f(x+a) - f(x)
as a is a natural number, the RHS is equal to af'(x). Thus,
(a+n)f'(x) - nf'(x+a) = af'(x)
And it follows that nf'(x) = nf'(x+a) for all natural n. As 0 is not a natural number, we can divide both sides by n, concluding that :
f'(x+a) = f'(x) for any integer a.
I.e d/dx( f(x+a) - f(x) ) = 0
Thus, f(x+a) - f(x) = c for all naturals a.
Using the initial functional equation, we conclude f'(x) = K and thus
f(x) = Kx+C.
Edit : I realised that I did basically the same thing as in the video. Nvm.
haha at least you could do it
I understood absolutely nothing from these scribbles, but this shit relaxes me. I think I may be into math :)
Thanks! Maybee more elegant would be to use Fundamental Calculus Theorem for f’(x) on x...x+n then mean value theorem to prove that f’(x) is a constant.
4:27 You went directly from
f'(x+1)-f'(x)=0
to
d/dx(f(x+1)-f(x))=0
Is the operator d/dx distributive for all real functions f?
I think that we are looking only for differentiable functions, so it is ok
It's linear
For all differentiable functions, yes. That's why you can differentiate polynomials (or other functions, for that matter) one term at a time.
@@RunstarHomer Thanks everyone. I forgot those rules/results. I'm sure a math professor of mine proved that at one point.
when you have (d/dx)(x^2+x) you do this: (d/dx)(x^2) + (d/dx)(x). That's what he did there. going back.
Great video, Barney Stinson
Can f be a linear function only?
0:30
TBH, it looks more like the formula of derivative of a function just without the " limit{n→0} " stuff
I feel like this was a really simple problem. It is just the definition of a derivative without the limit. So for any x, all points (x+N, f(x+N)) must be collinear. Already intuitively it must be a line. Suppose f'(x+c) != f'(x) for 0 < c < 1, then |f(x+c+k) - f(x+k)| ->infty for k in N, k->infty, so the function cannot be smooth
mmh, I agreay that intuitively the function is a line. But take f=exp. |f(x+c+k) - f(x+k)| = exp(x+k) * (exp(c) -1) and it tends to infinity with k.
This is how i tried to do it, but I found it tricky to prove the function had to be smooth. It does, because " f' = linear combination of f " with f differentiable implies f is smooth.
Wrong!
Could you be so nice to do something involving a consistency check for a Runge-Kutta method? For example, I can't really wrap my head around this task, but it does not have to be explicitely this. Anything similar should work.
Consider the Runge method
0 | 0 0
1/2a | 1/2a 0
---------------------------
| (1-a) a
and determine whether it is consistent or not. Also check if there exists values for a such that the method is consistent of order 3 despite it's tableau size.
Great work. Of course the intuitive answer can be argued as such: the instantenoues rate of change is identically equal to the average rate of change only for linear (and constant) functions, for all x in the domain of f(x).
This does not even resemble a proof. Essentially, you have rephrased the question of proof using English. There is no merit in doing so.
@@axemenace6637 He was not proving anything, just saying that the answer match the intuition.
@@axemenace6637 Bruh he wasn't trying to prove it. He was saying that you can think of it like this before doing a proof to kinda get an intuition for what the answer should be
You know....... When you look back at the problem it makes perfect sense, because the first order finite difference schemes approximates the derivative f'(x) assuming that f(x) is a first order polynomial. That's more or less the setup of this problem is, except n is a natural number not all non zero real number,
I'm guessing It should be possible to extend this to finite differences of higher orders, so for example all the solutions to the DE
f'(x) = (f(x+n)-f(x-n))/2n
should be all polynomials of order 2.
It's easy to see in the beginning that all linear functions satisfy the rule. But to prove that no more functions satisfy the rule is the more challenging part.
the proof was cool but the Intuition is quite simple: since n is not approaching zero, it wont be the instantaneous rate of change unless f(x) is straight and not curved. So f(x) must be linear.
What an anti-climax ? After all the great work, it turns out to be the humble linear function :-)
I solved this through the use of Taylor's Theorem.
We saw that f'(x) = [f(x+n)-f(x)]/n
This implies that nf'(x) = f(x+n) - f(x) so long as n !=0 (there is some convention about 0 being a natural number, but we'll discount that).
Rearranging, we have f(x+n) = f(x) + nf'(x)
We can similarly Taylor Expand f(x+n) with respect to the variable n, with n_0 = 0 [a Maclaurin Series]. Also note that the derivative of f(x+n) with respect to x and with respect to n are the same. By this, we have
f(x+n) = f(x)+nf'(x+n) + (1/2)n^2f''(x) + O(n^3)
Comparing the two results we have found, we see that
(1/2)n^2f''(x) + O(n^3) = 0
Since we are looking for functions that satisfy this for all n, we are left with f''(x) = 0.
Note that this second derivative condition is the strongest condition we get. Having the second derivative being zero immediately implies that all the higher order derivatives are 0.
This immediately implies that f(x) = a+bx for real numbers a,b
Observe the following:
f'(x) = b
[f(x+n)-f(x)]/n = [a+b(x+n) - (a+bx)]/n = bn /n = b
Thus our postulate is satisfied by these functions a+bx
From our initial derivative condition, we showed that the functions must be linear, moreover, every linear function satisfies this condition.
Also note that this was only done with the assumption that n!= 0, and nowhere did we assume that n was a natural number. Indeed, this proves something even stronger in that we can pick n to be any nonzero real number.
This is far from being a proof
1) the exercise asked for all differentiabile function, NOT 2 times differentiabile function
2) if you consider n to be continuous (and you used it in order to say that f"(x)=0 ) you are asking for function which satisfy a much more strict condition, so nobody tells you that there is some nonlinear function which do not satisfy the identity required for all n in R, but still, satisfies it for n in N
Example: if I ask for (differentiabile) functions which satisfy f(x+n)=f(x) for all x in R and for all n in R you end up with f being a constant; if you want that equality being satisfied for n in N you have much more functions, all function having period 1 (it isan infinity dimensional vector space of function).
We don’t know that it is twice differentiable
@@mario_veca You do know that it is twice differentiable.. Since the derivative is a linear combination of differentiable functions f(x+n) and f(x), the derivative is differentiable. You can then use induction to show that it is infinitely differentiable.
However you do not know that the Taylor series is convergent, so you may not be able to expand ina Taylor series.
Wrong! n is a natural number not any real number.
Thank you. I don't know how this got into my recommended videos, but I do like category theory a good deal.
I'm not that familiar with the Putnam exam. It seemed obvious to me at the beginning that the solution was any linear or constant function. On the exam, would it be necessary to provide a rigorous proof like this one, or would it be sufficient to simply state that in order to meet the conditions presented, the function must have a constant rate of change?
You would need to prove it
I feel like whenever one answer is linear functions it ends up being the only answer. Im just conjecturing here but is there some kind of uniqueness theorem for functional equations when one solution is a linear function?
A beautiful way to do this is as follow :Since f' is a linear combination of differentiable function, f is twice differentiable. Take the initial equation and instead of f'(x)=1/n(f(x+n)-f(x)) write f'(x+n)=1/n(f(x+2n)-f(x+n)) then replace f'(x+n) with nf"(x)+f'(x) and f(x+2n) with 2nf'(x)+f(x) and finally f(x+n) with nf'(x)+f(x) thus you will get f"(x)=0, it's easy to go on from this.
Good explanation😀😀😀
Michael... could be used the Lagrange's Theorem to solve this problem? Thank you
which Lagrange's Theorem?
@@MichaelPennMath f'(c)=(f(b)-f(a))/(b-a) for a continuous and derivative function, being c a point in the interval (a, b). Making b=x÷n and a=x, then f'(c)=f'(x) and f"(c) is a constant value u. Then integration. f(x) = ux + v. Thank you
How/Where do I learn this?
I done this by other way:
if x=0: f'(0)=(f(n)-f(0))/n
f'(0)=tan(theta)
(f(n)-f(0))/n=tan(alpha)
So theta=alpha
Because theta is constant, alpha is constant too, so because alpha is constant f(x) is a straight line, so it's of the form ax+b
You only proved that points f(n) lie on a straight line, not that f(x) for any real x is on a straight line.
except for the last part(05:30), I understood everything and loved the proof
if you know that constant func derivative is zero and only if it is constant, then it is easy to prove that if two functions have the same derivative, then their difference must be constant. (he did it in the video) At last, if you dy/dx linear you will have a constant. So if you have df/dx = A, then f = Ax + C
well there is a much easier and more intuitive way to solve this. the "discrete version" of the differential quotient defined in the question is simply a secant of the curve, meanwhile its limit is the tangent of the curve. knowing this we can conclude and even prove that the set of linear functions is the only solution. because we can approach the same question from a different, but equivalent way: which functions are those whose tangent's slope at any given point is equal to the slope of an infinite number of other secants drawn from the same point? the line is the only geometrical structure which satisfies this since the line is the only geometrical object in which case the tangents are identical to the secants (so the tangents and the secants degenerate into the same object).
Nice explanation! Can you do putnam question of A5 as well?
Isnt sin(2πx) and cos(2πx) also solution?
What aobut periodic functions? f'(x+1)=f'(x) => f'(x) = sin(20x/pi)
That equation isn't your only constraint. You also need to use the defining property of such function (s) I.e. the question statement.
A purpose of the derivative is to linearize and it becomes more accurate on a function with h -> 0 for the formal def. The only class of functions that dont care about this limiting behavior is already linearized functions themselves. Is this sound reasoning?
Wat? Surely any function at all of the natural numbers has a derivative, provided theres no infinite values.
I mean, x^2 has a derivative in the reals, right? Why doesnt it have a derivative over the rationals?
If f(x)=ax+b-cos(2𝜋x), then f'(x)=a+sin(2𝜋x)=a+sin(2𝜋x+2𝜋n)=f'(x+n)
Is there a mistake ?
Your forgot the chain rule!
@@MichaelPennMath Oh ! Yes. It is on my sheet but I forgot to write it in my comment. But nothing changes : f'(x)=a+2𝜋sin(2𝜋x)=a+2𝜋sin(2𝜋x+2𝜋n)=f'(x+n)
You do have f'(x)=f'(x+n) here so f(x+n)-f(x) is a constant but that's all you get. In the exercise you need to assume that f verifies the original equation to get f'(x)=C.
I approached it with a method that is bit more mathematically sophisticated and systematic. I observe that if h(x) and g(x) are solutions then all linear combinations, Af(x)+Bg(x), are solutions.
A little play indicates that Ax+B is a solution. So I can write f(x)=g(x)+f''(0)x+f(0). Where g(x) is also a solution but with g'(0)=0 and g(0)=0. Then write $g(x)=\int p(k)e^(ikx) dk $. Plug that in and you discover that p(k) =0 when k!= 0. So g(x) is at most a constant and thus 0.
Why did he write it down just until n=2 ? Is it enough to demonstrate that the equation is satisfied for all whole n ?
it would be actually! If you wanna be more formal about it you can prove it by induction
The fact that f satisfies the equation for all n is the assumption.
He only needed to write it for n = 1 and 2 because it gave enough necessary conditions to narrow down the solution f.
After proving that f is necessary an affine function, he should have proved that affine functions satisfy the equation but it's quite simple.
This can also be easily deduced by doing a Fourier transform of the equation
Can you really? I don't see how.
Could you also have trigonometric functions (with period of 1) that 'look' linear from far? I mean like
x + sin(x) or cos(x) - x or something. Would that even be possible?
No, that's one of the last steps.
I thought that. It applies to the f(X+n) = constant part but not the original eqn.
@@mcwulf25 they dont satisfy f' being constant
What about functions that are periodic, with period of 1.
They also satisfy f'(x+1) - f'(x) =0.
Like f(x) = sin(2pi * x)
Yeah, the proof is incomplete as is. To fix it, you would need to use the same process but instead of substituting 1 and 2 as n, use n and 2n. If you work it out, you will get f’(x)=f’(x+n) and this will narrow the solution to only linear functions. I hope this helps!
Yes, but they don't satisfy that f'(x) = f(x+1)-f(x). This allows concluding that f''(x) = 0, which doesn't hold for periodic functions.
Thank you for sharing this video!
I agree that this would be a more elementary proof if Michael showed that the property was satisfied by all affine functions (which is what he means when he says "linear functions"). But I don't agree that it's incomplete as he presents it. He's appealing to previous results: you can prove using the Mean Value Theorem that the only continuous functions that have derivative identically 0 are constant--and then you can cite that result any time you want without proving it again. Similarly, the Mean Value Theorem implies that the only continuous functions that have constant derivative are affine functions. And then you can cite that result any time you want without having to prove it again. This is what he means when he says "by elementary differential calculus."
Also, for the people thinking about periodic functions with period 1: it's true that those functions will satisfy the property f(x+1)-f(x)=0, but it is not true that they satisfy the original property from the statement of the problem. Such functions will have f(x+n)-f(x)=0 for all x and for all n, but they will not have f'(x)=0 for all x (otherwise, they would be constant functions...because Mean Value Theorem). This is exactly the point that No Way Haze makes below: Michael shows that, if a function satisfies Property A, then it also satisfies Property B; that doesn't mean that any function satisfying Property B also satisfies Property A.
By mathematical induction, f'(x) = f'(x+n)
Just put n tending to infinity and apply lhopital's rule, the RHS becomes a constant limit
How do you know that as n approaches infinity f(x+n) also approaches infinity? You can't use l'hospitals rule here.
And also n is a discrete variable
Such an easy Putnam problem... instant solve...
So in this proof you essentially only used the fact f'(x) = f(x+1)-f(x) = (f(x+2)-f(x))/2 and didn't need the statement for higher n. But what if we only assume f'(x) = f(x+1)-f(x) ? In other words, is there a differentiable function f: R -> R that satisfies f'(x) = f(x+1) - f(x) but is not linear? I guess that at least for infinitely differentable functions there shouldn't be any, but I couln't prove it yet.
Oh, that solution is waaaay easier than the one I found.
the tangent line must intersect all a+n, if its not tangent to some a+n then a+n+1 intersects two different tangent lines which is impossible, so f' is periodic with period 1 so d/dx(f(x+1)-f(x))=0 so f(x+1)-f(x)=C, f(x+1)-f(x)/1 = f'(x) so f'=C and f(x)=Cx+D
Is this proof wrong:
I saw that the right side of the original equation was the limit def. of a derivative so I recognized that it must be the average rate of change over an interval of [x, n]. Assuming there is a function whose derivative at one point is the same as its average rate of change from one point to another arbitrary point exists, this implies that any change in the second point won't cause the original equality to become false. A function that does this must have the same derivative everywhere because if not, then changing the second point will make the original equality false. The only function whose derivative is constant every where is a linear function f(x) = mx + b.
I thought it might be wrong because I didn't use the fact that n (which I referred to as the 'second point') is element of the natural numbers, even though that isn't necessary for my explanation.
Can somebody be tell me why he doesn't have to show this for more than n=1 and n=2. It's sure he's right but it's just bugging me
It is one of the conditions for this problem. If it works for every number n, then picking 2 numbers n will just be good enough.
@@tonymontana9221 ok thanks but why couldn't say n=3 and n=4 produce different additional properties giving a more general solution for f'(x). I strongly suspect they don't but I thought he would do an induction step or something to show this and only this solution for all n. Apologies if I'm not getting this
@@markkennedy9767 The hypothesis say that for every n, the function f must satisfy a given property. Using the cases n=1 and n=2, he derives a NECESSARY condition that all solutions must satisfy, namely that they are straight lines. Then he says he is done, but he should have checked that, in fact, all straight lines satisfy the hypothesis, which means that being a straight line is a SUFFICIENT condition, hence proving that the functions that satisfy the hypothesis are, precisely, the straight lines.
This means that the solution to this problem is exactly the same as the solution to the problem relaxing the condition "for all n" to only "for n=1 and n=2".
It is incorrect that linear functions are the only solutions. Namely, this system is linear time invariant for which in general the solutions are often of the form exp(a x). Plugging that into the initial differential equation yields a=(-W_k(-1/e)-1)/n, with W_k(x) the kth Lambert-W function. It can be noted that for k=-m and k=m+1 yields complex conjugate values (with positive real part), which means that f(x) could also be a linear combination of exponentially growing oscillations.
So your value a depends on n ? Do you understand that the equation must be satisfied for any natural number n ?
Great video! Why did the question say for all n rather than just n=1 and n=2?
To allow other approaches and to disguise the solution
Question tell slope of the function remains constant. Hence straight lines.
You got my subscription right now
At 4:11 you could have just set it equal to a constant rather than your whole random ramble, and in general although this is a nice proof, I think there are much simpler ways to do this
What are you talking about ?
I think I have a simpler solution. If f(x+n) grows to infinity then make n go to infinity in f’(x)=(f(x+n)-f(x))/n and apply l’Hospital with n as the variable and get f’(x)=f’(x+inf)=f’(inf). It follows that f’(inf) exists and is finite and as this is true for all x it follows that f’(x) is constant. Therefore f(x) is a linear function.
If f(x+n) does not go to infinity then it is either bounded or oscilates between +/- infinity or infinity and some finite values. If it is bounded then as n->inf we get f’(x)=0 which means f is constant which is a particular case of linear equation. It is easy to show it cannot oscilate as if it oscilates then f’(x) must be 0 for the equation to hold for all n, which is a contradiction. Qed
You cant use L'H if you got a discrete variable I guess
And since the functional eq. only holds for n in N, we cant switch to continous variables
When we are looking just at the right hand side of the board at the end of the video so what about f'(x)=sin(2*pi*x), which also satisfies f'(x+1)-f'(x)=0 while not being constant. Of course we won't get a valid solution for the problem with this f'(x) so the proof on the right side is not flawless.
Under-rated comment. This proof has an important hole
No, the proof is fine. In the last line he used the problem hypothesis that f(x + 1) - f(x) = f'(x), combined with f(x + 1) - f(x) = c (which 1-periodic funcions would indeed satisfy) to get f'(x) = c (which they would not).
He was talking about the function g, where g'(x) = f'(x+1) - f'(x), and not f. Since g'(x) = 0, then g(x) = c. That's why f(x+1) - f(x) is constant. What he wrote on the third line would still be satisfied with the function you gave; f'(x) = sin(2πx), where f(x+1) - f(x) = -1/(2π) cos(2πx + 2π) +1/(2π) cos(2πx) = 0, which is a constant in R. The proof is complete.
nice vid man, liked it.⚡
This is beautiful
I made a stupid infinite matrix equation for a vector of all the coefficients of a Taylor series from the x^2 term. And i found all of them have to be zero. So I'm left with the x^1 x^0 terms. It was overly complicated, the way i went about it.
Need to check if every implication is actually an "if and only if".
Unnecessarily hard solution: let P(x,n) be the assertion of the problem. Then P(x,n+1) compared with P(x+1,n) and then sending n to infinity implies f’(x+1)=f’(x). Notice that then f’ is periodic, and hence since P(x,n) holds, f’ is bounded (as f is continuous).
Then we use the fundamental theorem of calculus: f(x)-f(0) is the integral from 0 to x of f’(t). But this equals floor(x) times integral f’(t), plus a bounded term. Dividing by x and sending x to infinity, we conclude that lim f(x)/x exists (and equals integral f’(t) from 0 to 1).
Now we just take n to infinity in our original equation. The RHS converges to a limit L independent of x, while the left is simply f’(x). Hence f’ constant, and f is affine.
Notice that this shows we only need the property to hold for sufficiently large n.
Shouldn't you check your work and prove that f satisfies the differential equation for all n in the natural numbers
Since not all steps are reversible, the proof is incomplete. One should verify directly that the linear functions indeed satisfy the condition.
But it wasn’t a good place to stop???
Maaan, I really do need to get to study right now
And a quick verification shows...
f(x)=cx+d;
f(x+n)=c(x+n)+d;
f'(x)= [f(x+n)-f(x)]/n = (cx+cn+d-cx-d)/ n = cn/n = c (QED)
A consequence of this is that the derivative of any smooth continuous LINEAR function does NOT depend on N (i.e "dx" (or delta x)), so we dont even need to think of it as a LIMIT tending to 0. The only time we need to think of it as a limit tending to 0 is for degree 2 or higher. (Quadratic, Cubic etc, as there it DOES depend on N). :)
Q: Would it work for f(x) = |x| ?? Strictly speaking no as mod x is not smooth it has a sharp point at 0 where is not differentiable, so we would have to include a domain of validity e.g x > 0 or x < 0 for it to make sense... (it is "piecewise" continuous though but not smooth)
Great mr go on
What about f(x) = sin(2*x*pi) and f(x) = cos(2*x*pi)? These will have the same condition, f(x) = f(x+1), and will affect your answer.
They dont satisfy the functional equation
I'm a little bit concerned about the last part of the proof, maybe you could elaborate it a bit more.
You say, that from f'(x+1)-f'(x)=0 follows d/dx(f(x+1)-f(x))=0, so the difference must be constant, which of course is correct. But consider the counterexample for c=0:
f(x) =sin(2pi*x)
f'(x+1) - f(x)'=2pi*(cos(2pi*x+2pi) - cos(2pi*x)) = 0
The condition f'(x+1) - f'(x) = 0 just means that the derivative of the function is periodic. So you would have to rule out all of the non linear but periodic functions in order to complete the proof.
He does. After concluding that f(x+1)-f(x) is a constant, he goes back to the equation f'(x) = f(x+1) - f(x) and replaces the right hand side with said constant.
@@shaevor5680 I don't see this.
f'(x+1)=f'(x) is satisfied by periodic function, and f(x+1)=f(x) also, so how we exclude such function?
@@markryback3797 The initial equation satisfied by f is that (for n = 1) f'(x) = f(x+1)-f(x)
He proves that f(x+1)-f(x) is constant, therefore f'(x) is constant
Your sine function doesnt satisfy f'(x) = f(x+1) - f(x), which he did use in his very next step
I saw the answer 2 seconds after the question, but I just couldn't prove it in a formal way. The difficulty of this question is the formal proof.
I wish all putnam problems are easy as this one
It was the very first equation taught to start with differentiation aka first principle 😀
for me i found that f" is defined since f'(x)=f(x+1)-f(x) and f"(x)=f'(x+1)-f'(x)
then i worked with f'(x+1)
since f'(x)=f(x+1)-f(x) we get f'(x+1)=f(x+2)-f(x+1).....(1)
since 2f'(x)=f(x+2)-f(x) we have 2f'(x)+f(x)=f(x+2) .....(2)
since f'(x)=f(x+1)-f(x) we have f'(x)+f(x)=f(x+1)....(3)
using (2) and (3) in (1) we get f"(x)=0
hence f(x)=ax+b
but notice that what we have done is true just for n=1 and n=2 and we need to check that this holds true for all n in IN
we have nf'(x) =na and f(x+n)-f(x)=a(x+n)+b-ax-b=na
hence the solutions of the problem are under the form f(x)=ax+b
You should mention that f is twice differentiable since f'(x) = f(x+1) - f(x). This implies that f' is diff. (RHS is diff.)
Thank you for the solution. It looks so obvious. However, I am still confused how f(x) = cos 2πx agrees to f'(x) = f'(x+1), but it does not solve the initial equation.
same. that's where i got lost (and still am). a function where the slope is the same as the slope at x+1 made me think of trig function. how is it that an answer to the intermediary step is not an answer to the original problem... i'm confused.
So where is the confusion exactly?
Trig functions may satisfy f'(x+1) = f'(x) but as you pointed out, we got further restrictions
The step at 5:09 is the 'neck breaker' for the trigs
It's not done yet! You need to check that the linear functions satisfy all conditions! Otherwise you will lose points!
Why can't f'(X) be a wave function. Eg f'(X) = cos(2πx) then f'(X+1) = cos(2πx+2π) = cos (2πx)
Actually forget that. Doesn't work with the original eqn.
I think the prove is incomplete because d/dx(f(x+1)-f(x)) = 0 *CAN’T* get you a linear function. A sin function with period 1 also satisfies that.
I come up with a very different approach. The right part of the equation can’t be written in a integral of f’(x)/n from x to x+n. Let’s randomly pick some x, say 1. The left part is an integral of f’(1)/n from 1 to 1+n, and the right side can be written as f’(x)/n from 1 to 1+n. So we know that f’(x) = f’(1), which is some constant. Therefore, the function must be linear.
The right part of the equation can’t be written in a integral of f’(x)/n from x to x+n. Let’s randomly pick some x, say 1
The left part is an integral of f’(1)/n from 1 to 1+n"
What does this mean ?
You can write (f(x+n)-f(x))/n as integral(f(t)/n, for t = x to x+n) indeed (I think the assumptions on f are sufficient)
Then you can change x if you want, if you put x = 1, you get integral(f(t)/n, for t = 1 to 1+n)
You can't assign a value to the variable t inside the integral
His proof is valid, you just skipped some steps.
The function f(x+1)-f(x) definitely has to be constant. Your sine finction satisfies this.
But it does not satisfy f'(x) = f(x+1) - f(x), which he used in the next step to get f' is constant
Seems like LMVT.
Wow, great proof!
I have an alternative solution: Linear functions. It’s trivial
I was thinking more in terms of taylor series of f(x+n), but that assumes infinite differentiability :(
Then I pondered that f(x) = [x]*f'(x-[x]) + f(x-[x]) --- (1)
So, this becomes the study of a real valued function f in the domain [0,1).
It's easy to deduce that f'(0) = f(1) - f(0)
Let's assume that for some 0 < h < 1, f'(h) f(1) - f(0) (used to denote not equals sign)
This would mean that f(1+h) f(h) + f(1) - f(0)
But from (1) f(1+h) = f(1) - f(0) + f(h), which leads to a contradiction.
This means that for all 0
I don't think it's obvious that the Taylor series of f converges so I don't know if it's a valid approach.
Two words: Laplace transforms...
Would write this as f(x+n) = f(x) + nf'(x). Now this is clearly a line when n can take any value, but only naturals are given. Now observe f'(x+1) = f'(x) + 1f"(x) and (f(x+1+n) - f(x+1))/n = f'(x). By task request, both LHS have to be equal and thus f"(x) = 0, so f has the form f(x) = ax + b (integrate twice). It is easy to show any values for a and b will do.
Now how to come up with this? I initially let f(x) be anything, say g(x) between 0 and 1 and reconstructed the rest of f from the (rearranged) task equation. this gives you f(x) = g(x - z) + zg'(x - z) where z=floor(x). Now the task gave us an equation so I computed the LHS and the RHS of that equation. This gives you g"(x - z) = 0 and f"(x) = g"(x - z) = 0. Now g is essentially just f restricted to 0..1 so the whole argument can be done with f itself instead of g. Also n occurs twice in different roles but we can choose a simple value like 1 in one occasion. Actually could even have done that for both n, but it seemed more obvious to let one n just stay.
All of that just to get a: y = mx + b, lol
What about negative axis .as n belongs to N
Natural numbers are positive integer numbers (0 included)
WTF? I saw the answer right away by looking at the statement. I immediately noticed it was linear functions only, because I am a genius, would that be a valid answer?
😂😂😂
I am touched by you
I mean 'Not physically'