The Student Room Group

The Proof is Trivial!

Scroll to see replies

Solution 117

Let α\alpha be a solution to λp+λqλ=0\lambda^p+\lambda^q-\lambda =0.

Since f(xp)=f(x)p+αqf(x^p)=f(x)^p+\alpha^q and f(yq)=f(y)q+αpf(y^q)=f(y)^q+\alpha^p we have f(xp+yq)=f(xp)+f(yq)αf(x^p+y^q)=f(x^p)+f(y^q)-\alpha. Set h(z)=f(z)αh(z)=f(z)-\alpha gives h(x+y)=h(x)+h(y)h(x'+y')=h(x')+h(y') and hence f(x)=ax+αf(x)=ax+\alpha since f,hf,h cont.

It is now clear that a{1,0,1}a\in\{-1,0,1\} if p,qp,q are odd and a{0,1}a\in\{0,1\} otherwise. If a0a\neq 0 then we require α=0\alpha =0, if a=0a=0 it is easily checked that α\alpha has three possible values when maxp,q\max p,q is even and two when maxp,q\max p,q is odd ((both these cases include α=0\alpha=0 of course))



One of my favourite series questions:

Problem 119***

n=0(2nn)1\displaystyle \sum_{n=0}^{\infty} \binom{2n}{n}^{-1}
(edited 10 years ago)
Reply 821
Solution 119

We use generating functions.

Observe (2nn)1=n22n(2n1)×(2n2n1)1\displaystyle \dbinom{2n}{n}^{-1}= \frac{n^{2}}{2n(2n-1)} \times \dbinom{2n-2}{n-1}^{-1}
Hence 2(2n1)(2nn)1=n(2n2n1)1\displaystyle 2(2n-1) \dbinom{2n}{n}^{-1}= n \dbinom{2n-2}{n-1}^{-1}
Thus n=12(2n1)(2nn)1xn=n=1n(2n2n1)1xn\displaystyle \sum_{n=1}^{\infty} 2(2n-1) \dbinom{2n}{n}^{-1}x^{n} = \sum_{n=1}^{\infty} n \dbinom{2n-2}{n-1}^{-1}x^{n}
4n=0n(2nn)1xn2n=0(2nn)1xn+2=n=0(n+1)(2nn)1xn+1\displaystyle 4\sum_{n=0}^{\infty} n\dbinom{2n}{n}^{-1}x^{n} - 2\sum_{n=0}^{\infty} \dbinom{2n}{n}^{-1}x^{n}+2 = \sum_{n=0}^{\infty} (n+1)\dbinom{2n}{n}^{-1}x^{n+1}
F(x)=n=0(2nn)1xn\displaystyle F(x) = \sum_{n=0}^{\infty} \dbinom{2n}{n}^{-1}x^{n}.
Further, 4xF(x)2F(x)+2=x(xF(x))\displaystyle 4xF'(x)-2F(x)+2=x(xF(x))', which is equivalent to (4xx2)F(x)=(x+2)F(x)2(4x-x^{2})F'(x)=(x+2)F(x)-2.
Linear differential equation, with variable coefficients. We employ Lagrange's method. After solving this equation (it is too late here, so I am omitting the details (I may add these details in tomorrow)), we obtain F(1)=43+2π93\displaystyle F(1)= \frac{4}{3}+\frac{2\pi}{9\sqrt{3}}.
Original post by Mladenov
Solution 119


Bravo! :biggrin: I took a somewhat different route, if you're interested.

n0(2nn)1=n0(2n+1)Γ2(n+1)Γ(2n+2)=n0(2n+1)B(n+1,n+1)\displaystyle \sum_{n\geq 0} \binom{2n}{n}^{-1}=\sum_{n\geq 0} \frac{(2n+1)\Gamma^2(n+1)}{ \Gamma (2n+2)}=\sum_{n\geq 0} (2n+1)\text{B}\big (n+1,n+1\big)

f(α)=01n0α2n+1xn(1x)ndx=01αdx1α2x(1x)\displaystyle f(\alpha )=\int_0^1 \sum_{n\geq 0}\alpha^{2n+1}x^n(1-x)^n\,dx =\int_0^1 \frac{\alpha\,dx}{1-\alpha^2x(1-x)}

f(1)=011+xx2(x2x+1)2dx\displaystyle f'(1)=\int_0^1 \frac{1+x-x^2}{(x^2-x+1)^2}\,dx which is very easy.
(edited 10 years ago)
Oh and here is a quick alternative solution to 108:

Solution 108

α,β\alpha, \beta are integer roots to the eq. α+β4pq+1\alpha+\beta|4pq+1\Rightarrow exactly one of α,β\alpha,\beta is odd/even. Let α\alpha be the odd root:

(4pq+1)α=(p2+q2)(α2+1)(4pq+1)\alpha =(p^2+q^2)(\alpha^2+1)

LHS is odd, RHS is even, hence α\alpha cannot exist. So the polynomial is not a quadratic p=q=0\Rightarrow p=q=0
(edited 10 years ago)
Reply 824
Original post by Lord of the Flies
I took a somewhat different route, if you're interested


Superb. I would have never come up with this solution, for when I saw the binomial coefficient, I instantly started thinking of combinatorial solution.

The following problem is inspired by your profile picture.

Problem 120***

Evaluate: cosx1x2(x2+a)dx\displaystyle \int_{-\infty}^{\infty} \frac{\cos x -1}{x^{2}(x^{2}+a)}dx, where a>1a > 1.
Solution 120

a2cosx1x2(x2+a)dx=0cosx1x2dx(1)0cosxdxx2+a(2)+0dxx2+a(3)\displaystyle\frac{a}{2}\int_{-\infty}^{\infty} \frac{\cos x-1}{x^2(x^2+a)}\,dx=\underbrace{ \int_0^{ \infty} \frac{\cos x-1}{x^2}\,dx}_{(1)}-\underbrace{\int_0^{\infty} \frac{\cos x\,dx}{x^2+a}}_{(2)}+\underbrace{\int_0^{\infty} \frac{dx}{x^2+a}}_{(3)}

(1):    0cosx1x2dx=0sinxxdx\displaystyle (1):\;\;\int_0^{ \infty} \frac{\cos x-1}{x^2}\,dx=-\int_0^{\infty}\frac{\sin x}{x}\,dx

Unparseable latex formula:

\displaystyle \begin{aligned} w(t)=\int_0^{\infty}\frac{\sin tx}{x}\,dx\Rightarrow\mathcal{L}\{w(t)\} &=\int_0^{\infty}e^{-st}\int_0^{\infty}\frac{\sin tx}{x}\,dx\,dt\\&=\int_0^{\infty}\frac{1}{x}\int_0^{\infty}e^{-st}\sin tx\,dt\,dx\\&=\int_0^{\infty} \frac{1}{x}\left( \frac{x}{x^2+s^2} \right)\,dx \\&=\frac{\pi}{2s}



L1{π2s}=π20cosx1x2dx=π2\displaystyle\mathcal{L}^{-1} \left\{\frac{\pi}{2s}\right\} =\frac{\pi}{2}\Rightarrow \int_0^{ \infty} \frac{\cos x-1}{x^2}\,dx=-\frac{\pi}{2}

(2):    z(t)=0costxdxx2+adxL{z(t)}=0est0costxdxx2+adxdt=01x2+a0estcostxdtdx=01x2+a(sx2+s2)dx=ss2a(0dxx2+a0dxx2+s2)=π2a(1s+a)\displaystyle \begin{aligned}(2):\;\; z(t)=\int_0^{\infty} \frac{\cos tx\,dx}{x^2+a}\,dx\Rightarrow \mathcal{L} \{ z(t)\} &=\int_0^{\infty}e^{-st}\int_0^{\infty}\frac{\cos tx\,dx}{x^2+a}\,dx\,dt\\&=\int_0^{\infty}\frac{1}{x^2+a}\int_0^{\infty}e^{-st}\cos tx\,dt\,dx\\&=\int_0^{\infty} \frac{1}{x^2+a} \left(\frac{s}{x^2+s^2} \right)dx\\&=\frac{s}{s^2-a}\left(\int_0^{\infty}\frac{dx}{x^2+a}-\int_0^{\infty} \frac{dx}{x^2+s^2}\right)\\&= \frac{\pi}{2\sqrt{a}}\left( \frac{1}{s+\sqrt{a}}\right)\end{aligned}

L1{1s+a}=eat0cosxdxx2+a=π2aea\displaystyle\mathcal{L}^{-1} \left\{\frac{1}{s+\sqrt{a}} \right\} = e^{-\sqrt{a}t} \Rightarrow \int_0^{\infty} \frac{\cos x\,dx}{x^2+a}=\frac{\pi }{2\sqrt{a}e^{\sqrt{a}}}

(3):    0dxx2+a=π2a\displaystyle (3):\;\;\int_0^{\infty}\frac{dx}{x^2+a}=\frac{\pi}{2\sqrt{a}}

Therefore cosx1x2(x2+a)dx=πaa(1a1ea)\displaystyle\int_{-\infty}^{\infty} \frac{\cos x-1}{x^2(x^2+a)}\,dx=\frac{\pi}{a \sqrt{a}} \left(1-\sqrt{a}-\frac{1}{e^{\sqrt{a}}}\right)
Reply 826
Original post by Lord of the Flies
Solution 120


You would agree that Laplace is indeed quite useful for this problem, would you not?
I suspect that there is a complex analysis solution, but I am not sure if it is rather laborious.

Problem 121*** It is not that awful.

Evaluate sign(x)sign(y)ex2+y22sin(xy)dxdy\displaystyle \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} {\rm sign}(x){\rm sign}(y)e^{-\frac{x^{2}+y^{2}}{2}}\sin (xy) \,dx \,dy

Problem 122*** This is tough, unless one has studied analytic number theory.

Let n1(mod2)(1)n12lognn\displaystyle \sum_{n \equiv 1 \pmod 2} (-1)^{\frac{n-1}{2}}\frac{ \log n}{\sqrt{n}}, and n1(mod2)(1)n121n\displaystyle \sum_{n \equiv 1 \pmod 2} (-1)^{\frac{n-1}{2}}\frac{1}{\sqrt{n}}. Find an explicit form for (n1(mod2)(1)n12lognn)(n1(mod2)(1)n121n)1\displaystyle \left(\sum_{n \equiv 1 \pmod 2} (-1)^{\frac{n-1}{2}}\frac{ \log n}{\sqrt{n}} \right)\left(\sum_{n \equiv 1 \pmod 2} (-1)^{\frac{n-1}{2}}\frac{1}{\sqrt{n}} \right)^{-1}.
(edited 10 years ago)
Problem 123***

Prove that x816 x^8 \equiv 16 (Mod p) is solvable for every prime p.
Reply 828
Solution 123

For p=2p=2 the problem is trivial. We suppose p3p \ge 3. Note that xna(modp)x^{n} \equiv a \pmod p is solvable if and only if ap1gcd(n,p1)1(modp)\displaystyle a^{\frac{p-1}{\gcd (n,p-1)}} \equiv 1 \pmod p. To prove this assertion, we introduce gg - primitive root (modp)\pmod p. Let agi(modp)a \equiv g^{i} \pmod p and xgj(modp)x \equiv g^{j} \pmod p. We then have gjngi(modp)g^{jn} \equiv g^{i} \pmod p. This is equivalent to jni(modp1)jn \equiv i \pmod {p-1}. Let k=gcd(n,p1)k= \gcd(n,p-1). If i0(modk)i \equiv 0 \pmod k then jni(modp1)jn \equiv i \pmod {p-1} is solvable and ap1kg(p1)ik1(modp)\displaystyle a^{\frac{p-1}{k}} \equiv g^{\frac{(p-1)i}{k}} \equiv 1 \pmod p. If i≢0(modk)i \not\equiv 0 \pmod k, then jni(modp1)jn \equiv i \pmod {p-1} is not solvable and ap1kg(p1)ik≢1(modp)\displaystyle a^{\frac{p-1}{k}} \equiv g^{\frac{(p-1)i}{k}} \not\equiv 1 \pmod p.
Hence we have to prove that 24p1gcd(8,p1)1(modp)\displaystyle 2^{4\frac{p-1}{\gcd (8, p-1)}} \equiv 1 \pmod p, which is obvious unless p1(mod8)p \equiv 1 \pmod 8. However, in this case (2p)=1\left(\frac{2}{p}\right)=1; thus x22(modp)x^{2} \equiv 2 \pmod p is solvable and we are done.
...alright then.

Problem 124

Evaluate
Unparseable latex formula:

\tau_p = \displaystyle\sum_{k=0}^{p-1}\Big{(}\frac{k}{p}\Big{)} e^{\frac{2\pi i k}{p}}



Where
Unparseable latex formula:

\Big{(}\frac{k}{p}\Big{)}

is the legendre symbol.
(edited 10 years ago)
Reply 830
Some of these questions are getting a little silly (for the intended audience). Laplace transforms? Legendre symbols? These are things encountered in the second or third year of a good university. Having said that, if people are happy and able to solve them, by all means be my guest :smile:
Solution 121

sgnxsgnyexp(x2+y22)sinxydxdy\displaystyle\int_{-\infty}^{\infty} \int_{-\infty}^{\infty} \text{sgn}\, x\,\text{sgn}\, y \,\exp \left(-\frac{x^2+y^2}{2}\right)\sin xy\,dx\,dy

=400exp(x2+y22)sinxydxdy=4\displaystyle\int_0^{\infty} \int_0^{\infty}\exp \left(-\frac{x^2+y^2}{2}\right)\sin xy\,dx\,dy

=40π20rexp(r22)sin(r22sin2α)drdα=4\displaystyle\int_0^{\frac{\pi}{2}} \int_0^{\infty} r\exp \left(-\frac{r^2}{2}\right)\sin \left(\frac{r^2}{2}\sin 2\alpha\right)\,dr\,d\alpha

=40π2[11+sin22αexp(r22)(sin(r22sin2α)+sin2αcos(r22sin2α))]0dα=4\displaystyle\int_0^{\frac{\pi}{2}} \left[ -\frac{1}{1+\sin^2 2\alpha}\exp\left(-\frac{r^2}{2}\right)\left(\sin \left(\frac{r^2}{2}\sin 2\alpha\right) +\sin 2\alpha \cos\left(\frac{r^2}{2}\sin 2\alpha\right) \right)\right]_0^{\infty}d\alpha

=40π2sin2αdα1+sin22α=4\displaystyle\int_0^{\frac{\pi}{2}} \frac{\sin 2\alpha\,d\alpha}{1+\sin^2 2\alpha }

=80tdtt4+6t2+1=8\displaystyle\int_0^{\infty} \frac{t\,dt}{t^4+6t^2+1}

=2ln(3+22)=\displaystyle\sqrt{2}\ln \big(3+2\sqrt{2}\big)

In retrospect I am not sure switching to polar was the best idea, since some of the working is a bit tedious, but whatever.
Reply 832
Solution 124

Denote F(p)=k=0p1(kp)e2kiπp\displaystyle F(p)= \sum_{k=0}^{p-1} \left(\frac{k}{p}\right)e^{\frac{2ki\pi}{p}}. Hence we have (F(p))2=F(p)F(p)=(k=0p1(kp)e2kiπp)(m=0p1(mp)e2miπp)\displaystyle (F(p))^{2}=F(p)\overline{F(p)}= \left( \sum_{k=0}^{p-1} \left(\frac{k}{p} \right)e^{\frac{2ki\pi}{p}} \right) \left( \sum_{m=0}^{p-1} \left(\frac{m}{p} \right) e^{-\frac{2mi\pi}{p}}\right). Let ll be such that kml(modp)k \equiv ml \pmod p. Hence
(k=0p1(kp)e2kiπp)(m=0p1(mp)e2miπp)=m=1p1l=1p1(lp)e2im(l1)πp=p1+m=1p1l=2p1(lp)e2im(l1)πp=p1+l=2p1(lp)=p\begin{aligned} \displaystyle \left( \sum_{k=0}^{p-1} \left(\frac{k}{p} \right)e^{\frac{2ki\pi}{p}} \right) \left( \sum_{m=0}^{p-1} \left(\frac{m}{p} \right) e^{-\frac{2mi\pi}{p}}\right)&= \sum_{m=1}^{p-1} \sum_{l=1}^{p-1} \left(\frac{l}{p} \right) e^{\frac{2im(l-1)\pi}{p}} \\& = p-1+ \sum_{m=1}^{p-1} \sum_{l=2}^{p-1} \left(\frac{l}{p} \right) e^{\frac{2im(l-1)\pi}{p}} \\&= p-1 + \sum_{l=2}^{p-1} \left(\frac{l}{p} \right) \\&= p \end{aligned}
Therefore k=0p1(kp)e2kiπp=±p\displaystyle \sum_{k=0}^{p-1} \left(\frac{k}{p}\right)e^{\frac{2ki\pi}{p}} = \pm \sqrt{p}


Original post by Lord of the Flies
Solution 121
In retrospect I am not sure switching to polar was the best idea, since some of the working is a bit tedious, but whatever.


This integral turned out to be an annoying computation (I have also solved it using polar coordinates). I regret posting it, since most probably there is no concise solution.

Problem 125**

Let a1,a2,...,ana_{1}, a_{2},..., a_{n} be nn students. Some of these students know each other. Show that we can split these students into two groups such that if given student knows mm students from his or her group, then he or she knows at least mm students from the other group.

Problem 126***

Let f:[0,1]Rf : \left[0,1\right] \to \mathbb{R} be a continuous non-decreasing function. Show that 1201f(x)dx01xf(x)dx121f(x)dx\displaystyle \frac{1}{2}\int_{0}^{1} f(x)dx \le \int_{0}^{1} xf(x)dx \le \int_{\frac{1}{2}}^{1} f(x)dx.
(edited 10 years ago)
Reply 833
This isn't particularly fair, but whatever here goes (they're pretty :smile: ):

Plot r=ecos(θ)2cos(4θ)+sin7(θ/12)r=e^{\cos(\theta)}-2\cos(4\theta)+\sin^7(\theta/12)

Plot r=sin(sin(θ))2sin(4θ)+sin2(θ/19)r=\sin(\sin(\theta))-2\sin(4\theta) + \sin^2(\theta/19)
Original post by shamika
This isn't particularly fair, but whatever here goes (they're pretty :smile: ):

Plot r=ecos(θ)2cos(4θ)+sin7(θ/12)r=e^{\cos(\theta)}-2\cos(4\theta)+\sin^7(\theta/12)

Plot r=sin(sin(θ))2sin(4θ)+sin2(θ/19)r=\sin(\sin(\theta))-2\sin(4\theta) + \sin^2(\theta/19)


Well, according to Wolfram Alpha:Polar1.jpg and Polar2.jpg
Reply 835
Original post by Zephyr1011
Well, according to Wolfram Alpha:Polar1.jpg and Polar2.jpg


Yep :smile:

The first is called the butterfly curve - the second is my own creation after playing around with it a bit
Original post by shamika
Yep :smile:

The first is called the butterfly curve - the second is my own creation after playing around with it a bit


What do you call this then? :colone:

Spoiler

(edited 10 years ago)
Reply 837
Original post by ukdragon37
What do you call this then? :colone:

Spoiler



LOL! At least you could stick my curve into Wolfram Alpha easily (which is what I was intending :tongue:)

What is it?
Original post by shamika
Some of these questions are getting a little silly (for the intended audience). Laplace transforms? Legendre symbols? These are things encountered in the second or third year of a good university. Having said that, if people are happy and able to solve them, by all means be my guest :smile:


I find it telling how the OP hasn't submitted a solution since about question 50, and we're now past question 120. This thread stopped being interesting (Or even accessible) for the vast majority of people quite a long time ago and now it seems very much to just be a battle of wits between Mladenov and Lord of the Flies.

(If this comes across as jealous, then that's probably because it is - I'd love to be able to even attempt the questions that are being thrown around lately! :lol: Unfortunately, the questions that are being thrown out are aimed at a very small audience indeed and just looking at the list in the OP it's very easy to see. It reminds me very strongly of what the STEP thread was like before Christmas.)
Reply 839
Original post by DJMayes
I find it telling how the OP hasn't submitted a solution since about question 50, and we're now past question 120. This thread stopped being interesting (Or even accessible) for the vast majority of people quite a long time ago and now it seems very much to just be a battle of wits between Mladenov and Lord of the Flies.

(If this comes across as jealous, then that's probably because it is - I'd love to be able to even attempt the questions that are being thrown around lately! :lol: Unfortunately, the questions that are being thrown out are aimed at a very small audience indeed and just looking at the list in the OP it's very easy to see. It reminds me very strongly of what the STEP thread was like before Christmas.)


France vs. Bulgaria.

Quick Reply

Latest