Math Challenge - February 2020

  • Challenge
  • Thread starter fresh_42
  • Start date
  • Featured
  • #1
fresh_42
Mentor
Insights Author
2021 Award
17,588
18,068
Questions

1.
(solved by @archaic ) Determine ##\lim_{n\to \infty}\cos\left(t/\sqrt{n}\right)^n## for ##t\in \mathbb{R}##.

2. (solved by @Antarres ) Let ##a_0,\ldots,a_n## be distinct real numbers. Show that for any ##b_0,\ldots,b_n\in\mathbb{R}##, there exists a unique polynomial ##p## of degree at most ##n## such that ##p(a_i)=b_i## for each ##i##.

3. (solved by @Antarres ) Let ##r(t)=(x(t),y(t))## be an arc-length parameterization of a smooth closed curve ##C## with length ##2\pi##. Let ##A## be the area enclosed by ##C##
a.) Using Green's formula, show ##A^2\leq\left(\int_0^{2\pi}x(t)^2dt \right)\ \left(\int_0^{2\pi}y'(t)^2 dt\right)##
b.) By translating ##C##, we may assume without loss of generality that ##\int_0^{2\pi}x(t) dt=0##. Use this assumption together with the Wirtinger inequality (question 1 of the January challenge) to show that ##A\leq\pi.##
c.) By examining the equality condition for the Wirtinger inequality (Problem No. 1 in 01/2020), show that ##A=\pi## can only happen if ##C## is a circle.

4. (solved by @Antarres ) Let ##f:[0,\infty)\to\mathbb{R}## be a continuous function such that the sequence of functions ##f_n(x)=f(x+n)## converges uniformly to a function ##g:[0,\infty)\to\mathbb{R}##. Show that ##f## and ##g## are uniformly continuous.

5.
a.)
(solved by @etotheipi ) Let ##A## = ##
\begin{bmatrix}
-1 & 0 \\
2 & 1
\end{bmatrix}
## Find ##A^{99}##, ##A^{2n}## and ##A^{2n + 1}##, ##n \in \mathbb{N}##
b.) (open) How would we conclude in case of any commutative ring using ideals? (##\operatorname{char} \neq 2##)

6. (solved by @Antarres )
a.) If ##a##,##b##,##k## are integers with ##b \neq 0## show that ##(a + kb, b) = (a,b)##
b.) We take the Fibonacci sequence ##(F_n)## (starting from the third term): ##1, 2, 3, 5, 8, 13, \dots##, where each term after the second one, is the sum of the two previous terms. If ##F_n## is the ##n-##th term of the sequence, show that every two consecutive Fibonacci numbers are coprime.

7.
a.)
(solved by @archaic ) If ##f: \mathbb{R} \to \mathbb{R}## is an integrable function in every closed interval of ##\mathbb{R}## show using calculus that
$$\int_{a}^{b} f(x)\,dx = \int_{a + d}^{b + d} f(x - d)\,dx$$
with ##a \leq b## and ##d \geq 0##.
b.) (open) The function ##\varphi\, : \,\mathbb{R}^2 \longrightarrow \mathbb{R}^2## with ##\varphi(t,r)=(t(r+2),t^2-r)## is injective on ##U:=(0,1)\times (-1,1)\,.## Show that ##\varphi\, : \,U\longrightarrow V:= \varphi(U)## is a diffeomorphism.
Next let ##f\, : \,\mathbb{R}^2\longrightarrow \mathbb{R}## be integrable over ##V##. Write
$$
\int_V f\,d\lambda = \int_{\ldots}^{\ldots} \int_{\ldots}^{\ldots} \ldots f(\ldots\, , \,\ldots)\,dr\,dt
$$
and calculate the area of ##V##.

8. (solved by @julian ) Calculate ##\displaystyle{\sum_{k=1}^\infty} \dfrac{1}{\binom{2k}{k}}##

9. (solved by @Antarres ) Let ##a## be an integer and ##p## an odd prime which does not divide ##a##. The left multiplication
$$
\lambda_{a,p}\, : \,\mathbb{Z}_p^\times \longrightarrow \mathbb{Z}_p^\times \, ; \,x \longmapsto ax \operatorname{mod} p
$$
is then a permutation on ##\{\,1,\ldots,p-1\,\}\,.## Prove
$$
\left(\dfrac{a}{p}\right) = \operatorname{sgn}\left(\lambda_{a,p}\right)
$$

10. (solved by @suremarc and @Antarres ) Let ##\mathcal{H}## be a real Hilbert space and ##\beta## a continuous bilinear form, ##\mathcal{H}^*## its dual space of continuous functionals on ##\mathcal{H}##, and ##\beta(f,f)\geq C\|f\|^2>0.##
Prove that for any given continuous functional ##F \in \mathcal{H}^*## there is a unique vector ##f^\dagger \in \mathcal{H}## such that
$$
F(g)=\beta(f^\dagger,g)\quad \forall\,\,g\in \mathcal{H}
$$


1580532399366.png


High Schoolers only

11.
Answer the following questions:
a.) (solved by @mmaismma ) How many knights can you place on a ##n\times m## chessboard such that no two attack each other?
b.) (solved by @Not anonymous ) In how many different ways can eight queens be placed on a chessboard, such that no queen threatens another? Two solutions are not different, if they can be achieved by a rotation or by mirroring of the board. (For this part there is no proof required.)

12. (solved by @Not anonymous ) Determine (with justification, but without explicit calculation) which of
a.) ##1000^{1001}## and ##{1002}^{1000}##
b.) (solved by @etotheipi ) ##e^{0.000009}-e^{0.000007}+e^{0.000002}-e^{0.000001}## and ##e^{0.000008}-e^{0.000005}##
is larger.

13. (solved by @etotheipi , @Not anonymous)
a.) Let ##A=(-2,0)\, , \,B=(0,4)## and ##M=(1,3)\,.## What is ##\alpha = \sphericalangle (AMB)##?
b.) Let ##C=(-1,2+\sqrt{5})\, , \,D=(-1,2-\sqrt{5})## and ##M=(1,3)\,.## What is ##\beta = \sphericalangle (CMD)##?

14. (solved by @Not anonymous ) Find the exact formula of the function ##f(x) =\sup_{t \in \mathbb{R}}(2tx - t^2)##, ##x \in \mathbb{R}##.

15. (solved by @etotheipi ) In what way does the oscillation period of a pendulum change, if the suspension pivot moves
a.) vertically up with acceleration ##a##,
b.) vertically down with acceleration ##a < g##,
c.) horizontally with acceleration ##a##?
 
Last edited:
  • Like
Likes etotheipi, JD_PM and berkeman

Answers and Replies

  • #2
5. Let ##A## = ##
\begin{bmatrix}
-1 & 0 \\
2 & 1
\end{bmatrix}
##. Find ##A^{99}##, ##A^{2n}## and ##A^{2n + 1}##, ##n \in \mathbb{N}##

##A^{2} =
\begin{pmatrix}
-1 & 0 \\
2 & 1 \\
\end{pmatrix}

\begin{pmatrix}
-1 & 0 \\
2 & 1 \\
\end{pmatrix}
= I##

##A^{99} = ({A^{2}})^{49}A = I^{49}A = IA = A##

##A^{2n} = ({A^{2}})^{n} = I^{n} = I##

##A^{2n+1} = A^{2n}A = IA = A##
 
Last edited by a moderator:
  • Like
Likes Erico Romaric and QuantumQuest
  • #3
archaic
688
210
1. Determine ##\lim_{n\to \infty}\cos\left(t/\sqrt{n}\right)^n## for ##t\in \mathbb{R}##.
$$\begin{align*}
\lim_{n\to\infty}\cos\left(\frac{t}{\sqrt{n}}\right)^n&=\lim_{n\to\infty}e^{n\ln\left(\cos\left(\frac{t}{\sqrt{n}}\right)\right)}\\
&=\lim_{n\to\infty}e^{n\ln\left(1-\frac{t^2}{2n}+o(\frac{1}{n})\right)}\\
&=\lim_{n\to\infty}e^{n\left(-\frac{t^2}{2n}+o(\frac{1}{n})\right)}\\
&=e^{-\frac{t^2}{2}}
\end{align*}$$
 
  • Like
Likes Abhishek11235 and Erico Romaric
  • #4
archaic
688
210
7. If ##f: \mathbb{R} \to \mathbb{R}## is an integrable function in every closed interval of ##\mathbb{R}##, show using calculus that $$\int_{a}^{b} f(x)\,dx = \int_{a + d}^{b + d} f(x - d)\,dx$$with ##a \leq b## and ##d \geq 0##.
$$\begin{align*}
I&=\int_{a}^{b} f(x)\,dx,\text{ let } u = x+d \Leftrightarrow x=u-d\\
&=\int_{a+d}^{b+d} f(u-d)\,du
\end{align*}$$
Just call ##u## as ##x##. This seemed to be too straightforward. Did I miss something?
 
  • #5
QuantumQuest
Science Advisor
Insights Author
Gold Member
926
483
##A^{2} =
\begin{pmatrix}
-1 & 0 \\
2 & 1 \\
\end{pmatrix}

\begin{pmatrix}
-1 & 0 \\
2 & 1 \\
\end{pmatrix}
= I##

##A^{99} = ({A^{2}})^{49}A = I^{49}A = IA = A##

##A^{2n} = ({A^{2}})^{n} = I^{n} = I##

##A^{2n+1} = A^{2n}A = IA = A##

Well done @etotheipi. It's a very nice shortcut way for this particular case. However, there is a more general way we can solve problems like this. I won't tell what is it but if anyone else wants to try the problem and come up with a correct solution, he / she'll also get credit.
 
Last edited:
  • #6
Well done @etotheipi. It's a very nice shortcut way for this particular case. However there is a more general way we can solve problems like this. I won't say what it is but if anyone else wants to try the problem and come up with a correct solution, he / she'll also get credit.

Naïve me should have known there be more to it! Of course, I have no idea what...
 
  • #7
QuantumQuest
Science Advisor
Insights Author
Gold Member
926
483
Naïve me should have known there be more to it! Of course, I have no idea what...

I wouldn't call you naive. According to the educational background you have in your info, you're doing really well. It's just that, what is needed for the solution I said in post #5, is usually taught in the first year(s) of College / University for mathematicians and of course, as far as I know. Things may be different in some countries for both High School and College /University.
 
  • #8
QuantumQuest
Science Advisor
Insights Author
Gold Member
926
483
$$\begin{align*}
I&=\int_{a}^{b} f(x)\,dx,\text{ let } u = x+d \Leftrightarrow x=u-d\\
&=\int_{a+d}^{b+d} f(u-d)\,du
\end{align*}$$
Just call ##u## as ##x##. This seemed to be too straightforward. Did I miss something?

What I ask for, is an approach / solution using some sort of limits. I say "using calculus" in the wording of the question, which is not clear enough but if I make it totally clear, I'll give the way of the solution ;)
 
Last edited:
  • #9
Not anonymous
141
58
13. a.) Let ##A=(-2,0), B=(0,4)## and ##M=(1,3)##. What is ##\alpha = \sphericalangle (AMB)##?
b.) Let ##C=(-1,2+\sqrt{5})\, , \,D=(-1,2-\sqrt{5})## and ##M=(1,3)##. What is ##\beta = \sphericalangle (CMD)##?

A silly doubt but I have to ask because I had never heard of "spherical angle" till I saw the symbol ##\sphericalangle## in the quoted question. I could find some articles on the web describing spherical angle but my understanding is still vague. To the doubt - given 3 points, there would be infinite number of spheres on whose surface those lie. Had the 3 points in the question been 3D points specified w.r.t. some center of sphere, the problem would be fully specified. With 2D points and no mention of the reference sphere, I do not understand how to decide on the sphere to choose. Any additional hints that you can provide?
 
  • #10
fresh_42
Mentor
Insights Author
2021 Award
17,588
18,068
A silly doubt but I have to ask because I had never heard of "spherical angle" till I saw the symbol ##\sphericalangle## in the quoted question. I could find some articles on the web describing spherical angle but my understanding is still vague. To the doubt - given 3 points, there would be infinite number of spheres on whose surface those lie. Had the 3 points in the question been 3D points specified w.r.t. some center of sphere, the problem would be fully specified. With 2D points and no mention of the reference sphere, I do not understand how to decide on the sphere to choose. Any additional hints that you can provide?
Don't blame me for the word LaTeX uses to show an angle! Read it as 2D ##\angle (AMB)##. I just liked the symmetry of ##\sphericalangle (AMB)## more. Handwritten, I would have used
1580661770152.png

Anyway, it is a plane angle meant in the problem.
 
  • #11
Not anonymous
141
58
14. Find the exact formula of the function ##f(x) =\sup_{t \in \mathbb{R}}(2tx - t^2), x \in \mathbb{R}##.

The simple nature of the function that I get as the solution gives me the suspicion that I might have misunderstood the question :confused: . Posting that solution anyway

For a fixed value of ##x##, we find the maxima for ##g(t) = (2tx - t^2), t \in \mathbb{R}##. At the maximum points, ##g'(t) = 0 \implies 2x - 2t = 0 \implies x = t##. This is the maximum and not the minimum because ##g''(t) = -2## is negative (alternative explanation - there is no finite minimum; as ##g(t) \rightarrow \infty## as ##t## tends to ##\pm \infty## for any finite value of ##x##). Substituting this value of ##t## for which maximum is attained, we get ##\sup_{t \in \mathbb{R}}(2tx - t^2) = x^2##. Therefore, ##f(x) = x^2##
 
  • Like
Likes Abhishek11235 and QuantumQuest
  • #12
Don't blame me for the word LaTeX uses to show an angle! Read it as 2D ##\angle (AMB)##. I just liked the symmetry of ##\sphericalangle (AMB)## more.
In that case,
a.) ##\vec{MA} \cdot \vec{MB} = (-1)(-3) + (1)(-3) = 0 \implies \alpha = \frac{\pi}{2}##
b.) ##\vec{MC} \cdot \vec{MD} = (-2)(-2) + (\sqrt{5} -1)(-\sqrt{5} -1) = 0 \implies \beta = \frac{\pi}{2}##
 
  • #13
fresh_42
Mentor
Insights Author
2021 Award
17,588
18,068
In that case,
a.) ##\vec{MA} \cdot \vec{MB} = (-1)(-3) + (1)(-3) = 0 \implies \alpha = \frac{\pi}{2}##
b.) ##\vec{MC} \cdot \vec{MD} = (-2)(-2) + (\sqrt{5} -1)(-\sqrt{5} -1) = 0 \implies \beta = \frac{\pi}{2}##
Right. Can you also give a geometric argument?
 
  • #14
Right. Can you also give a geometric argument?

Does cosine rule suffice?

##\cos{\theta} = \frac{a^{2} + b^{2} - c^{2}}{2ab}##

where for the part a), ##a = 3\sqrt{2}, b= \sqrt{2}, c= 2\sqrt{5}##

and for part b), ##a = \sqrt{10 + 2\sqrt{5}}, b =\sqrt{10 - 2\sqrt{5}}, c = 2\sqrt{5}##

These both give ##\cos{\theta} = 0 \implies ## both angles are ##\frac{\pi}{2}##.
 
  • #15
fresh_42
Mentor
Insights Author
2021 Award
17,588
18,068
Does cosine rule suffice?

##\cos{\theta} = \frac{a^{2} + b^{2} - c^{2}}{2ab}##

where for the part a), ##a = 3\sqrt{2}, b= \sqrt{2}, c= 2\sqrt{5}##

and for part b), ##a = \sqrt{10 + 2\sqrt{5}}, b =\sqrt{10 - 2\sqrt{5}}, c = 2\sqrt{5}##

These both give ##\cos{\theta} = 0 \implies ## both angles are ##\frac{\pi}{2}##.
I thought of classical geometry - another one - but it seems there are many ways to see it.
Let's see whether someone comes up with a third method.
 
  • #16
hilbert2
Science Advisor
Insights Author
Gold Member
1,562
579
For problem 2:

For instance, if there are 3 points ##a_i## and ##b_i## each, the question is whether you can always find a polynomial ##P(x) = c_2 x^2 + c_1 x + c_0## such that

##c_2 a_{1}^2 + c_1 a_1 + c_0 = b_1 ,##
##c_2 a_{2}^2 +c_1 a_2 + c_0 = b_2 ,##
##c_2 a_{3}^2 + c_1 a_3 + c_0 = b_3##

This is equivalent to the linear system

##\begin{bmatrix}a_{1}^2 & a_1 & 1 \\ a_{2}^2 & a_2 & 1 \\ a_{3}^2 & a_3 & 1\end{bmatrix}\begin{bmatrix}c_2 \\ c_1 \\ c_0\end{bmatrix} = \begin{bmatrix}b_1 \\ b_2 \\ b_3\end{bmatrix}##

and it has a solution if the coefficient matrix is invertible, i.e.

##\left|\begin{array}{ccc}a_{1}^2 & a_1 & 1 \\ a_{2}^2 & a_2 & 1 \\ a_{3}^2 & a_3 & 1\end{array}\right|\neq 0##

The determinant of that type is called a Vandermonde determinant, and it is always nonzero if numbers ##a_i## are distinct, no matter what's the ##n\in\mathbb{N}## in the size of the square matrix ##n\times n##. This proves the claim.
 
  • #17
I thought of classical geometry - another one - but it seems there are many ways to see it.
Let's see whether someone comes up with a third method.

The line passing through points ##A## and ##M## has equation ##y=x+2##, and intercepts the y-axis at ##y=2##. Let's call this point ##Q##. Now let ##Q## and ##M## be the two ends of a diameter of a circle of radius ##1##, which we construct about a centre of ##(0,3)##. The point ##M##, ##(1,3)## then lies on the circumference on this circle and using circle theorems we deduce that ##\angle BMQ## is a right angle. By extension, since ##A##, ##Q## and ##M## are on the same straight line, the necessary angle is also right.
 
  • #18
fresh_42
Mentor
Insights Author
2021 Award
17,588
18,068
The line passing through points ##A## and ##M## has equation ##y=x+2##, and intercepts the y-axis at ##y=2##. Let's call this point ##Q##. Now let ##Q## and ##M## be the two ends of a diameter of a circle of radius ##1##, which we construct about a centre of ##(0,3)##. The point ##M##, ##(1,3)## then lies on the circumference on this circle and using circle theorems we deduce that ##\angle BMQ## is a right angle. By extension, since ##A##, ##Q## and ##M## are on the same straight line, the necessary angle is also right.
Close, and on the right track, but it's a little bit easier. What are ##AB## and ##CD##?
 
  • #19
Close, and on the right track, but it's a little bit easier. What are ##AB## and ##CD##?

Appears they are also the endpoints of the diameter of a circle, e.g. in part a) a circle of radius ##\sqrt{5}## and centre ##(-1,2)##. And as the distance from ##(-1,2)## to ##(1,3)## is also ##\sqrt{5}##, the result follows much more easily!
 
  • #20
Infrared
Science Advisor
Gold Member
965
538
@hilbert2 This is right, but the identity for the Vandermonde determinant is a more difficult result than the original question!

There is a very simple solution.
 
  • #21
Not anonymous
141
58
Don't blame me for the word LaTeX uses to show an angle! Read it as 2D ##\angle (AMB)##. I just liked the symmetry of ##\sphericalangle (AMB)## more. Handwritten, I would have used
View attachment 256496
Anyway, it is a plane angle meant in the problem.

Thanks for clarifying. I had initially found the solution assuming plane angle but on noticing the LaTeX code of the symbol when posting the solution, I stopped and went to find what spherical angle means but stopped again after getting confused about the choice of sphere.

For both the questions, the answer is 90°.

13a. Lengths of line segments ##AB##, ##BM## and ##AM## are ##\sqrt{20}, \sqrt{2}, \sqrt{18}## respectively and it may be noticed it ##AM^2 + BM^2 = 18 + 2 = 20 = AB^2## (in the equation, I used ##AB## to denote the length of line segment ##AB## and so on). By Pythagoras theorem, this implies that the triangle is right angled with ##AB## as the hypotenuse. ##∠(AMB)## being its opposite angle must be 90°.

13b. ##C=(−1,2+√5),D=(−1,2−√5)## and ##M=(1,3)##. Lengths of the line segments are ##CD= 2\sqrt{5} = \sqrt{20}, DM = \sqrt{2^2 + {(1+√5)}^2}, CM = \sqrt{2^2 + {(1-√5)}^2}##. ##DM^2 + CM^2 = (4 + (1 + 5 + 2√5)) + (4 + (1 + 5 - 2√5)) = 20 = CD^2##. Again by Pythagorean theorem, this implies that ##\Delta CDM## is a right-angled triangle with ##CD## as the hypotenuse. ##∠(CMD)## is the hypotenuse's opposite angle and must be 90°.
 
  • #22
fresh_42
Mentor
Insights Author
2021 Award
17,588
18,068
Appears they are also the endpoints of the diameter of a circle, e.g. in part a) a circle of radius ##\sqrt{5}## and centre ##(-1,2)##. And as the distance from ##(-1,2)## to ##(1,3)## is also ##\sqrt{5}##, the result follows much more easily!
They are both diameters of ##(x+1)^2+(y-2)^2=5## and ##M## is part of the circle, too. The statement follows with the theorem of Thales.
 
  • #23
If we transform into the accelerating frame of the pivot, and consider the extra fictitious force contributing to an effective weight, we obtain the following.
a.) ##g_{eff} = a + g \implies T = 2\pi \sqrt{\frac{l}{a+g}}##
b.) ##g_{eff} = g - a \implies T = 2\pi \sqrt{\frac{l}{g - a}}##
c.) ##g_{eff} = \sqrt{a^{2} + g^{2}} \implies T = 2\pi \sqrt{\frac{l}{\sqrt{a^{2} + g^{2}}}}## about ##\theta = \arctan{\frac{a}{g}}## from the vertical
I don't know whether this argument is sufficient, though, or whether you were after a derivation from first principles especially for part ##c##!
 
Last edited by a moderator:
  • Like
Likes QuantumQuest
  • #24
hilbert2
Science Advisor
Insights Author
Gold Member
1,562
579
@hilbert2 This is right, but the identity for the Vandermonde determinant is a more difficult result than the original question!

There is a very simple solution.

Ok, I guess it's something similar to finding a polynomial with zeros at ##a_i## by forming a product of binomials ##(x-a_i)##.
 
  • #25
StoneTemplePython
Science Advisor
Gold Member
1,260
597
@hilbert2 This is right, but the identity for the Vandermonde determinant is a more difficult result than the original question!
I happen to like Vandermonde matrices, so I'll point out there is a very easy, computation free, and sneaky finish here.
note: the LaTeX below renders fine locally where I wrote it, but a lot of it is not rendering on PF for reasons I don't understand

for a Vandermonde matrix
$$V = \begin{bmatrix} 1 & 1 & \dots & 1 & 1 \\ v_1 & v_2 & \dots & v_{n-1} & v_{n}\\ v_1^2 & v_2^2 & \dots & v_{n-1}^2 & v_{n}^2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ v_{1}^{n-1} & v_{2}^{n-1} & \dots & v_{n-1}^{n-1} & v_{n}^{n-1}\end{bmatrix}$$

its immediate that the matrix is singular if ##v_i = v_j## for ##j\neq i## because one column is a copy of the other. To prove that this is the only way the matrix is singular, suppose first n-1 columns are distinct, insert a free variable ##x## in the final column and compute the determinant

$$\det\left( \begin{bmatrix}1 & 1 & \dots & 1 & 1 \\v_1 & v_2 & \dots & v_{n-1} & x\\v_1^2 & v_2^2 & \dots & v_{n-1}^2 & x^2 \\\vdots & \vdots & \ddots & \vdots & \vdots \\v_{1}^{n-1} & v_{2}^{n-1} & \dots & v_{n-1}^{n-1} & x^{n-1}\end{bmatrix}\right) = p(x) = k\cdot\prod_{i=1}^{n-1}(x-v_i)$$

which is a degree n-1 polynomial and by inspection has exactly n-1 distinct roots and no more. so ##p(x) \neq 0## for ##x\not \in \{v_1,v_2,...,v_{n-1}\}## because the product of finitely many non-zero numbers is a non-zero number. This proves ##\det\big(V\big)\neq 0## if all columns are distinct.

(For avoidance of doubt, we know ##k\neq 0## say because, up to a sign, it is given by the leading n-1 x n-1 principal minor which is non-zero by induction hypothesis -- which is obviously ##= 1\neq 0## in the implicit 2x2 base case.)

I found the outlines of this in Feller vol 2 a while back, so maybe the argument is sophisticated in some sense but it really is quite simple and sneaky.
 
Last edited:
  • Like
Likes hilbert2 and Infrared
  • #26
fresh_42
Mentor
Insights Author
2021 Award
17,588
18,068
note: the LaTeX below renders fine locally where I wrote it, but a lot of it is not rendering on PF for reasons I don't understand
Inline LaTeX is abbreviated by ## = [itex], not by $. The reason is, that it is MathJax on websites, not LaTeX - there is no compilation possible, only rendering.
 
  • Like
Likes StoneTemplePython
  • #27
StoneTemplePython
Science Advisor
Gold Member
1,260
597
Inline LaTeX is abbreviated by ## = [itex], not by $. The reason is, that it is MathJax on websites, not LaTeX - there is no compilation possible, only rendering.
oh man. I mangled that one. Thanks.

There really should be a face palm emoji that I could apply to your post, since that's what I just did
 
  • #28
Antarres
170
81
a)
If there exists a number that divides both ##a## and ##b##, then it obviously divides ##a + kb##:
$$a = pd \qquad b = qd \Rightarrow a+kb = (p+kq)d$$ for some ##p, q \in \mathbb{Z}##. So we have that if ##d## is a common divisor of ##a## and ##b##, then it is also the common divisor of ##a+kb## and ##b##.
Conversely, if ##d## divides both ##a+kb## and ##b##, then:
$$a+kb = pd \qquad b=qd \Rightarrow a = a+kb - kb = (p-kq)d$$ for some ##p,q \in \mathbb{Z}##. So if ##d## is the common divisor of ##a+kb## and ##b## then it is also a common divisor of ##a## and ##b##. Since we have shown the equivalence here, it implies that common divisors of ##a+kb## and ##b## completely match with common divisors of ##a## and ##b##. So the same holds for the greatest common divisor.
Hence:
$$(a+kb) = (a,b)$$
as needed.
b)
Here we will just use the above statement in conjunction with the definition of Fibonacci sequence that fits our exercise, namely:
$$F_n = F_{n-1} + F_{n-2} \qquad n\geq 3 \qquad F_1 = 1 \quad F_2=2$$
We prove the assertion by induction:
Base(##n=3##): ##(2,3) = 1##, which holds trivially.
Assume the statement holds for all ##k## up to some number ##n##. We prove that it then holds for ##n+1##.
$$(F_{n+1},F_n) = (F_n + F_{n-1},F_n)$$
By induction hypothesis ##(F_n, F_{n-1}) =1##. But by a) part of the exercise (taking ##F_n = b##, ##k=1##, ##F_{n-1}=a##), ## (F_n + F_{n-1},F_n) = (F_{n-1},F_n) = 1##. This ends the induction, so the assertion is proved.
 
  • Like
Likes QuantumQuest and etotheipi
  • #29
Antarres
170
81
As @hilbert2 pointed out, using Vandermonde matrix property is enough to prove question #2. Here is maybe a simpler solution.
Since we just need to prove the uniqueness, assume the opposite, that two polynomials of degree ##n##, ##p## and ##q## have the property that ##p(a_i) = b_i## and ##q(a_i) = b_i##.
Then for all numbers from the given two sets, we have that:
$$p(a_i) - q(a_i) = 0$$
We construct a new polynomial ##r(x) = p(x) - q(x)##, which has ##n+1## roots as it is shown above. But by fundamental theorem of algebra, an ##n##-th degree polynomial can only have ##n## roots, so it follows that:
$$p(x) - q(x) \equiv 0$$
which shows that ##p## is unique.
 
  • #30
Infrared
Science Advisor
Gold Member
965
538
@Antarres Why is it enough to just show uniqueness? The Vandermonde determinant argument shows both existence and uniqueness (as long as you have some fact about the Vandermonde matrix).

Uniqueness does in fact imply existence in this case. Could you add why?
 
Last edited:
  • #31
mathwonk
Science Advisor
Homework Helper
11,391
1,626
hint for problem #2: consider the map taking a polynomial of degree ≤ n to its sequence of n+1 values at the given points. If this map is injective, it has been claimed it is also surjective. Do you know a situation in which such a claim is true?

alternate constructive approach: try first to find a polynomial of degree ≤ n which equals zero at every aj with j ≠ 0, but is not zero at a0.
 
  • #32
Antarres
170
81
I actually missread the question, so I wasn't considering existence, just uniqueness. So I will elaborate:
Finite dimensional vectors approach(more complicated one, I guess):

First way to prove the existence, is to consider the space of polynomials with degree ##\leq n## as a vector space. It is finite dimensional with dimension ##n+1## and basis ##x^i##, ##i =0, \dots, n##. We then create a map from this space onto ##\mathbb{R}^{n+1}##, real vector space of the same dimension.
The map takes ##n+1## parameters ##a_0, a_1, \dots, a_n##, and maps every polynomial from the polynomial vector space into a vector constructed from it's values at these parameters, that is, if we denote the polynomial space by ##P_n##, we have:
$$f: P_n \rightarrow \mathbb{R}^{n+1} \qquad f(P(x); a_0, \dots, a_n) = (P(a_0), \dots,P(a_n))$$
Polynomials in ##P_n## are given by a set of their coefficients: ##P(x) = (p_0, \dots, p_n)##, from which we observe that the map above preserves linearity.
Above, we have taken parameters to be constants, so the function is defined for a fixed set of parameters.
By proving uniqueness, we have asserted that the function above is injective. But because it is a linear mapping between two finite dimensional vector spaces of the same dimension, rank-nullity theorem implies that injectivity guarantees surjectivity.

This approach, if one is not familiar with the polynomial of degree ##\leq n## vector space, is implicitly using the Vandermonde matrix type of reasoning, should one choose to prove that the basis I have given is indeed a basis of the space. The approach below is more straightforward, and in tune with the uniqueness proof.

Constructive approach(simple one):

By fundamental theorem of algebra, every polynomial of ##n##-th degree has ##n## roots, so we can construct the following polynomial with our given set of numbers ##a_0, \dots, a_n##.
$$P(x) = \frac{(x-a_1)(x-a_2)\dots(x-a_n)}{(a_0 - a_1)(a_0 - a_2)\dots(a_0 - a_n)}b_0$$
This polynomial is zero for every value from the set except ##a_0##, and ##P(a_0) = b_0##. We can create similar polynomials separately for every ##a_i##, ##i=0,\dots, n##. Then the sum of such polynomials will have the property that ##p(a_i)=b_i## since for each ##a_i##, we'd have only one non-zero term in the sum, which is the one corresponding to the parameter ##a_i## we have on input.
 
  • #33
DEvens
Education Advisor
Gold Member
1,203
460
2. Let ##a_0,\ldots,a_n## be distinct real numbers. Show that for any ##b_0,\ldots,b_n\in\mathbb{R}##, there exists a unique polynomial ##p## of degree at most ##n## such that ##p(a_i)=b_i## for each ##i##.

Part 1) Existence.

Construct the co-location polynomial. The i'th term is as follows.

$$ P_i(x) = \frac{ (x- a_0) (x- a_1 ) ... b_i ... (x- a_n)}{ (a_i - a_0)(a_i - a_1 ) ( a_i-a_{i-1} ) (a_i-a_{i+1} ) ... (a_i - a_n) } $$

That is, in the numerator the ##(x-a_i)## term is replaced by ##b_i## and in the denominator the ##(a_i - a_i)## term is not there. The full polynomial is the following.

$$ P(x) = \sum_{i=0}^{n} P_i(x)$$

Clearly, by construction, ##P(a_i) = b_i##, and ##P(x)## is at most of degree n. It may be of lesser degree if the points happen to fall on a curve that is of lower order.

Part 2) Uniqueness.

Construct the matrix [a] as follows.

\begin{equation}
[a] = \left[
\begin{array} {ccccc}
1 & a_0 & a_0^2 & ... & a_0^n \\
1 & a_1 & a_1^2 & ... & a_1^n \\
& & ... & & \\
1 & a_n & a_n^2 & ... & a_n^n
\end{array}
\right]
\end{equation}

Construct a vertical vector of polynomial coefficients [C] , and a vertical vector [ b ] of the b values. (Being careful not to confuse the LaTeX here by putting the [ and ] too close to the letter b. Sigh.) Then make a polynomial P(a), and require it to give the b values, as follows.

$$ P(a) = [a][C] = [ b ] $$

Note that since the a values are distinct, the rows and columns of [a] are therefore not linearly dependent. Therefore the matrix [a] has an inverse. And we can then write the following.

$$ [C] = [a]^{-1} [ b ] $$

The components of the vector [C] are therefore the unique coefficients of the required polynomial.
 
  • #34
Infrared
Science Advisor
Gold Member
965
538
Above, we have taken parameters to be constants, so the function is defined for a fixed set of parameters.
By proving uniqueness, we have asserted that the function above is injective. But because it is a linear mapping between two finite dimensional vector spaces of the same dimension, rank-nullity theorem implies that injectivity guarantees surjectivity.

This approach, if one is not familiar with the polynomial of degree ##\leq n## vector space, is implicitly using the Vandermonde matrix type of reasoning, should one choose to prove that the basis I have given is indeed a basis of the space. The approach below is more straightforward, and in tune with the uniqueness proof.

Right! I'm not sure why you think you're using facts about the Vandermonde matrix though. The vector space ##\mathbb{P}_n## has dimension ##n+1## because ##1,x,\ldots,x^n## is a basis. The linear map ##\mathbb{P}_n\to\mathbb{R}^{n+1}, p\mapsto (p(a_0),\ldots,p(a_n))## is injective since, as you noted, if a polynomial of degree at most ##n## vanishes at ##n+1## distinct points, then it is the zero polynomial. So it is also surjective by rank-nullity. I'm pretty sure this is the simplest argument.

Note that since the a values are distinct, the rows and columns of [a] are therefore not linearly dependent.
How did you conclude that the columns are linearly independent? Anyway, existence and uniqueness are equivalent for this problem (the columns of a square matrix span if and only if they are linearly independent), so proving either part is enough.
 
  • #35
Antarres
170
81
Right! I'm not sure why you think you're using facts about the Vandermonde matrix though. The vector space ##\mathbb{P}_n## has dimension ##n+1## because ##1,x,\ldots,x^n## is a basis. The linear map ##\mathbb{P}_n\to\mathbb{R}^{n+1}, p\mapsto (p(a_0),\ldots,p(a_n))## is injective since, as you noted, if a polynomial of degree at most ##n## vanishes at ##n+1## distinct points, then it is the zero polynomial. So it is also surjective by rank-nullity. I'm pretty sure this is the simplest argument.
Well, you say that ##1,x,\ldots, x^n## is the basis, but in order to prove it, you have to prove linear independence of these functions, which basically boils down to a Vandermonde type determinant being non-singular(for concrete ##a##, I guess). So if you take this as a fact, then it is the simplest, but if you don't, you have to revert back, that's what I meant. Either way, yeah, injectivity implies surjectivity because of that argument.
 

Suggested for: Math Challenge - February 2020

  • Last Post
2
Replies
67
Views
6K
  • Last Post
2
Replies
60
Views
7K
  • Last Post
3
Replies
98
Views
9K
  • Last Post
Replies
33
Views
6K
  • Last Post
2
Replies
52
Views
8K
  • Last Post
3
Replies
104
Views
11K
  • Last Post
4
Replies
137
Views
13K
  • Last Post
5
Replies
156
Views
13K
  • Last Post
2
Replies
61
Views
8K
  • Last Post
5
Replies
150
Views
13K
Top