Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[MagmaMcFry]

A form of nerd-sniping: present a simple problem that can be trivially made much harder.

Why is there a glowing red conjecture on my forehead?

[Skyrunner]

I think this problem isn't solvable. Can someone confirm that?
Also, I left most of my problems at the hakwon (math cram school-like thing), so I have very few to present. If this is sufficiently interesting enough, I'll be posting more later x3

As always, no calcs. This one is probably a problem where calculators won't help.

Let {a_n} be a series.
Let S_n = a₁ + a₂ + ... + a_n.  (In other words, sigma k=1 to n, a_n)
Let a₁ = 1.
The equation

(S_n+1 - S_n-1 + a_n)² = 8a_na_n+1 + 4ⁿ

is true for any n, where n ≥ 2 and n is a natural number. Find the value of

lim_n→∞ ( a_n / (n * 2ⁿ) ).

[Sergarr]

My extremely low math skills tell me that it is 1 or close to it definitely 1.

Also, this is too easy. This equation can be pretty much solved in 4 steps.

[MagmaMcFry]

Actually, that limit can be anywhere between -1/2 and 1/2, or even not exist.
Proof: Let b_n be a_n/2ⁿ for all n. The given equality is then equivalent to |b_n+1-b_n|=1/2. The absolute sign is very important here and shows that the problem has multiple (a_n) solutions.

Therefore, for any series (c_n) with elements in {-1/2, 1/2} (but c₁ = +1/2), the sequence 2ⁿsigma(1,n,c_k) is a valid sequence of (a_n), for which a_n/(n*2ⁿ) converges to -1/2 + the limit percentage of positive c_k, which is obviously variable, and may not even exist.

Example 1: Let 0 <= p <= 1. Then c_n := 0.5*(-1)^{floor(n*p)-floor((n-1)*p)} generates a sequence (a_n) for which lim(a_n/(n*2ⁿ)) = 1/2 - p.

Example 2: Let p > 1. Then c_n := 0.5*(-1)^{floor(log_pn)} generates a sequence (a_n) for which the value of a_n/(n*2ⁿ) fluctuates between -(p-1)/2(p+1) and +(p-1)/2(p+1), so the limit doesn't exist.

[Sergarr]

Okay, I'll think about it. Although the uncertainty in determining a(n), I believe, is not intended, because then the problem doesn't make sense. I've got an equation a(n+1)=2^n+2a(n) which results in limit being 1, but now I see that the quadratic equation has the other solution, which makes this problem unsolvable, bleh.

[MagmaMcFry]

Okay, I'll think about it. Although the uncertainty in determining a(n), I believe, is not intended, because then the problem doesn't make sense. I've got an equation a(n+1)=2^n+2a(n) which results in limit being 1, but now I see that the quadratic equation has the other solution, which makes this problem unsolvable, bleh.

Even with your recursion, the limit would be 1/2, not 1.

[Brilliand]

Actually, that limit can be anywhere between -1/2 and 1/2, or even not exist.
Proof: Let b_n be a_n/2ⁿ for all n. The given equality is then equivalent to |b_n+1-b_n|=1/2. The absolute sign is very important here and shows that the problem has multiple (a_n) solutions.

Therefore, for any series (c_n) with elements in {-1/2, 1/2} (but c₁ = +1/2), the sequence 2ⁿsigma(1,n,c_k) is a valid sequence of (a_n), for which a_n/(n*2ⁿ) converges to -1/2 + the limit percentage of positive c_k, which is obviously variable, and may not even exist.

Example 1: Let 0 <= p <= 1. Then c_n := 0.5*(-1)^{floor(n*p)-floor((n-1)*p)} generates a sequence (a_n) for which lim(a_n/(n*2ⁿ)) = 1/2 - p.

Example 2: Let p > 1. Then c_n := 0.5*(-1)^{floor(log_pn)} generates a sequence (a_n) for which the value of a_n/(n*2ⁿ) fluctuates between -(p-1)/2(p+1) and +(p-1)/2(p+1), so the limit doesn't exist.

Note that 8a_na_n+1 + 4ⁿ can never be negative, so once |a_n/2^n| > [some threshold], a_n will either consistently increase (making the final limit 1/2) or consistently decrease (making the final limit -1/2).  If that never happens, then the final limit will be 0.

EDIT: No wait, that's wrong.  a_n can't change signs past that threshold, but it can still decrease, so it can drop below that threshold and change signs later.

[Another]

Has anybody noticed that that original recursive equation as stated is not connected to the given value of a₁ at all?

[Brilliand]

Has anybody noticed that that original recursive equation as stated is not connected to the given value of a₁ at all?

Yeah, but it doesn't affect the limit in the long run, so...

EDIT: Just tried applying the equation to a₁, and a₂ can be 0 or 4, a₃ can be -4, 4 or 8...

The (simpler form of the) general formula is a_n=b_n*2^(n-1) where |b_n-b_n-1|=1, in case anyone's wondering.  Divide a_n by 2^(n-1) to get the real position of a relative to how fast it moves.  With a₂ disconnected from a₁ as in the original formulation, b_n doesn't have to be a whole number or within any particular range (but it will approach the range -1<b_n/n<1 in the limit).

[da_nang]

-snip-

*Using the corrected choice 2*
Since I had time to kill, an answer that doesn't rely on using a graph or calculator:

Spoiler: Dirty work, P1 (click to show/hide)

(x₁,y₁):

|ln(x)/ln(2)| = x + 2

0<x<1:

ln(x)/ln(2) = -(x + 2)
x = e^{-(x + 2)*ln(2)}
x*e^x*ln(2) = 1/4
x*ln(2)*e^x*ln(2) = ln(2)/4

x = W(ln(2)/4)/ln(2)

W(z) is the Lambert W function

x>=1:

ln(x)/ln(2) = x + 2
x = e^(x+2)*ln(2)
x*e^-x*ln(2)= 4
-x*ln(2)*e^-x*ln(2) = -4*ln(2)

x = -W(-4*ln(2))/ln(2)

N.B. W(z) is not real-valued for z < -1/e

Assuming a > 1

ln(x)/ln(a) = x + 2
x = e^(x+2)*ln(a)
x*e^-x*ln(a) = a²
x = -W(-a²*ln(a))/ln(a)

a²*ln(a) > 1/e

a² > 1/ln(a^e)

Since a² < a^e for a > 1

a² > 1/ln(a²) > 1/ln(a^e)

If a > √e, then ln(a²) > 1 and 1/ln(a²) < 1. Since √3 < 2, then √e < √3 < 2

So, for a>=2, there is no solution for x >= 1

Thus x₁ = W(ln(2)/4)/ln(2), where ln(2)/4 > 0 and thus W(z) is the primary branch.
Since 0 < ln(2)/4 < e, then 0 < W(ln(2)/4) < 1 thus 0 < x₁ < 1/ln(2)

y₁ = W(ln(2)/4)/ln(2) + 2

Spoiler: Dirty work, P2 (click to show/hide)

(x₂,y₂):

|ln(x)/ln(3)| = x + 2

For 0<x<1:

ln(x)/ln(3) = -(x + 2)

x = e^-(x+2)*ln(3)
x*e^x*ln(3) = 1/9
x = W(ln(3)/9)/ln(3)

x₂ = W(ln(3)/9)/ln(3)
y₂ = W(ln(3)/9)/ln(3) + 2

Since ln(3)/9 > 0 then W(z) is the primary branch. Furthermore, ln(3) < 9, then ln(3)/9 < 1
Thus, 0 < W(ln(3)/9) < 1 and 0 < x₂ < 1/ln(3).

Since 3 > 2 (from Dirty work, P1), then this is the only solution.

Spoiler: Dirty work, P3 (click to show/hide)

(x₃, y₃):

x₃ > 1

ln(x)/ln(2) = 2 - x
x = e^(2-x)*ln(2)
x*e^x*ln(2) = 4

x₃ = W(4*ln(2))/ln(2) > 1, since 4*ln(2) > e thus W(4*ln(2)) > 1 and ln(2) < 1

y₃ = 2 - W(4*ln(2))/ln(2) < 1, since x₃ > 1

(x₄, y₄):
x₄ > 1

ln(x)/ln(3) = 2 - x
x = e^(2-x)*ln(3)
x*e^x*ln(3) = 9

x₄ = W(9*ln(3))/ln(3)

If W(9*ln(3)) > ln(3) then

since z = W(z)*e^W(z):

z > ln(3)*e^ln(3)
z > 3*ln(3)

Since z = 9*ln(3), this is true.

Thus x₄ > 1

y₄ = 2 - W(9*ln(3))/ln(3) < 1

Spoiler: Choice 1 (click to show/hide)

Is x₁ < x₂?

ln(2)/4 < ln(3)/9 ⇔ ln(2)/2² < ln(2+1)/(2+1)²

Let f(x) = ln(x)/x², x > 1
f'(x) = (x - 2x*ln(x))/x⁴
(Legal) zeroes at 1 - 2*ln(x) = 0 ⇔ x = √e < 2 (critical point)

Where is f(x) going for x>=2?

f'(e) = (e - 2e*ln(e))/e^4 = -1/e^3 < 0

Thus, f(x) is monotonously decreasing for x >= 2

Thus ln(2)/4 > ln(3)/9 and since W(z) is strictly monotonously increasing for x > -1/e in the primary branch, then this implies W(ln(2)/4) > W(ln(3)/9)

Therefore W(ln(2)/4)/ln(2) > W(ln(3)/9)/ln(2) > W(ln(3)/9)/ln(3)
i.e. x₁ > x₂.

Choice 1: False

Spoiler: Choice 3 (click to show/hide)

x₃y₄ < x₄y₃ |/(x₃x₄) (>0)

y₃/x₃ > y₄/x₄

(2-x₃)/x₃ > (2-x₄)/x₄

2/x₃ - 1 > 2/x₄ - 1

1/x₃ > 1/x₄

x₃ < x₄

W(4*ln(2))/ln(2) < W(9*ln(3))/ln(3)


Since 4*ln(2) < 9*ln(3), therefore W(4*ln(2)) < W(9*ln(3))

Thus W(4*ln(2))/ln(2) < W(9*ln(3))/ln(2) < W(9*ln(3))/ln(3)

Choice 3: True

Spoiler: Choice 2 (click to show/hide)

(x₃-x₄)/(x₂-x₁) = (y₄-y₃)/(y₂-y₁)
(y₂-y₁)/(x₂-x₁) = (y₄-y₃)/(x₃-x₄)

Since x₁ > x₂ (Choice 1) and x₄ > x₃ (Choice 2) then
(y2-y1)/(x2-x1) = (y4-y3)/(x3-x4) ⇔ -k_C = k_D, where k_C and k_D are the slopes of the lines C and D respectively.

k_C = 1
k_D = -1

-k_C = k_D
-1 = -1

Choice 2: True

[Sergarr]

"W(z) is the Lambert W function"

...what is the Lambert W function?

[Vector]

Oh yeah, something I've been wondering about.

Is the sequence 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, etc. something that can be written in closed form?

[ZetaX]

The problem is more to define "closed form" than to answer the question. Floor of something around sqrt(2n) should do, but I don't feel motivated to find the exact one (which exists).

[Vector]

Is there a formula where I pop in n and it pops out the term I want.

[Skyrunner]

I think I remember seeing an iterative form of that equation... ifyes, it can have an equation yhat pops out a number when inputted with a number