Math challenge! [NEW 12/5]

[Surlethe]

Solve this problem and write a formal solution. Either post it in the thread, or, more preferably, attach it to a post, scan it as an image and post it, or upload it to a free-download site.

Problem:



N.B.: the problem is not my creation. If there are enough entrants, I will reveal the source; not until then, though.

PS- Yes, I've already solved it.

[Kuroneko]

I remember solving this problem by proving a somewhat stronger result: Spoiler

Show that lim[ n!F_n(1) + ln(n) ] exists finitely.

which would imply an obvious value for your limit. I'm not sure whether that's the most straightforward way of solving your problem, however. Interestingly, treating n as a continuous variable does give (d/dn)[n!F_n(1)] = -Sumk>0 1/(n+k)², so L'Hospital's rule gives the same result, but justifying that approach to your source would have been more work than necessary.

[edit]Surlethe: I cut out the outline of my solution. If you want, I can PM or repost it, or try solving the above problem yourself.[/edit]

[Surlethe]

That's easy I think the real key to the problem is getting a firm handle on F_n(x).
Spoiler

By graphing 1/x, we see that for n > 1 sum_{k=2}^n 1/k < ln n < sum_{k=2}^n 1/[k-1], so 0 < ln n - sum_{k=2}^n 1/k < sum_{k=2}^n 1/[k-1] - 1/k = 1/n because it's a telescoping sum. So 0 < ln n - sum_{k=2}^n 1/k < 1; moreover, by an inspection of the graph, the sequence is monotonically increasing. So it converges finitely.

If I'm right, why don't you go ahead and repost your solution in spoilers?

[Kuroneko]

That's easy :) I think the real key to the problem is getting a firm handle on F_n(x).

Really? I figured that part was more straightforward--it had more algebraic gymnastics, but not much creativity. Although maybe that's because I already expected something the problem to have something to do with a certain well-known constant just from seeing seeing the problem statement. Spoiler

Let Gn= n!Fn. Here, all integrals will be over (0,x) unless otherwise stated. We show by mathematical induction that Gn = xn[log x - Hn], where Hn is the nth harmonic number. The initial n = 0 case follows from integration by parts: Int[ log t dt ] = x log x - Int[ t d(log t) ] = x(log x - 1), as well as the induction step:
Gn+1 = Int[ log t d{tn+1} - (n+1)tnHn dt ] = xn+1 log x - Int[ (1+(n+1)Hn)tn dt ] = xn+1[log x - Hn+1].
Hence n!Fn(1) = -Hn. It remains to show that lim[ -Hn + log n ] exists finitely (this is -γ).

Edit:

Spoiler

By graphing 1/x, we see that for n > 1 sum_{k=2}^n 1/k < ln n < sum_{k=2}^n 1/[k-1], so 0 < ln n - sum_{k=2}^n 1/k < sum_{k=2}^n 1/[k-1] - 1/k = 1/n because it's a telescoping sum. So 0 < ln n - sum_{k=2}^n 1/k < 1; moreover, by an inspection of the graph, the sequence is monotonically increasing. So it converges finitely.

You're right in limit follows from your first bound, but I doubt that graphing would have been acceptable to your source. Is there another way to establish it? Mine was a long the lines of: Spoiler

Consider Int01{1/(t+k) - 1/k} dt. The limit is a summation over k of those terms, which bounds it by a 1/k² series (up to mult. constant)--the latter considerably more tractable.

[Darth Yoshi]

Spoiler

F0(x) = ln x
lim(n->inf) Fn(x) = lim(n->inf) (xn/n!)ln x - 3xn/2n! = (xn/n!)*(ln x -3/2)
lim(n->inf) Fn(1) = (ln[1] - 3/2)/(inf)! = -3/2(inf)! = 0

Ergo:
lim(n->inf) n!Fn(1)/ln = (inf)!*0/ln(inf) = 0

I'm sure I've fucked up somewhere, though.

[Grog]

Spoiler

F1=xlnx-x
The integral of a xb lnx + c xb
is
a lnx xb + 1/(b + 1) + (-a + c) x b + 1/(b + 1)
We get a recursion
n!Fn(1)=-1/n!+(n-1)!Fn-1(1)
1!F1(1)=-1
and hence
n!Fn(1)=-1-1/2-...-1/n
aproximating the sum with the integral of 1/x we see that lim n!Fn(1)/ln(n)=-1 or something like that.

[Surlethe]

New math challenge(s)! As above, solve any or all of them and write formal solutions, then post in spoilers.

[1] Prove that e is irrational.

[2] Let f be a real-valued function on the plane such that for any square ABCD f(A) + f(B) + f(C) + f(D) = 0. Characterize f completely.

[EC] Extra credit challenge: Prove that pi is irrational!

The problem in the OP was from last year's Putnam exam.

[Kuroneko]

[2] Let f be a real-valued function on the plane such that for any square ABCD f(A) + f(B) + f(C) + f(D) = 0. Characterize f completely.

Spoiler

Imagine a 3x3 grid, with sixteen points and nine 1x1 squares giving nine linearly independent constraints. Adding every 1x1 square counts every vertex twice, except the corner ones, which are counted once. On the other hand, adding any three 2x2 squares counts every vertex once, except for a lone corner. Hence the corners are free, the four 2x2 squares represent three constraints, and the 3x3 square does not contribute at all. Of the sqrt(2)-sided squares, adding them all sans the one central square gives everything but the corners, so that they represent three constraints. Similarly, one of the two remaining sqrt(5)-sided squares is redundant. Since the twenty conditions form a linear system of rank 16, only the trivial solution exists.

[EC] Extra credit challenge: Prove that pi is irrational!

[EEC] Prove that e and pi are irrational using the same method.

[Darth Holbytlan]

[2] Let f be a real-valued function on the plane such that for any square ABCD f(A) + f(B) + f(C) + f(D) = 0. Characterize f completely.

Spoiler

For any point V, pick an arbitrary square ABCD centered on V and quarter it, forming a 3x3 grid of vertexes ([[APB],[QVR],[CSD]]). The total number of squares formed is 6: ABCD; the 4 small squares APQV, PBVR, QVCS, and VRSD; and the square PQRS formed at 45&deg;. The sum of f applied to the vertexes of the 4 small squares is 0, so the sum of f at all 9 points weighted by [[1,2,1],[2,4,2],[1,2,1]] is also 0. The sum of f applied to the vertexes of ABCD and twice the vertexes of PQRS is 0, and weights the vertexes by [[1,2,1],[2,0,2],[1,2,1]]. Subtract the two to find that 4f(V)=0, so f(V)=0. QED.

[Kuroneko]

That's neat, Darth Holbytlan. I should've resisted the urge to overconstrain it.

[Surlethe]

[EEC] Prove that e and pi are irrational using the same method.

Sure, as long as you don't use Euler's identity or complex numbers
Spoiler

Quick proof idea, as bedtime approaches: I'm trying to use the MacLaurin expansion of arccos and arccos(-1) = pi.