Problem of the Week #78 - September 23rd, 2013

[Chris L T521]

Thanks again to those who participated in last week's POTW! Here's this week's problem!

-----

Problem: Starting with the vertices $P_1(0,1)$, $P_2(1,1)$, $P_3(1,0)$, $P_4(0,0)$ on a square, we construct further points as shown in the figure below: $P_5$ is the midpoint of $P_1P_2$, $P_6$ is the midpoint of $P_2P_3$, $P_7$ is the midpoint of $P_3P_4$, and so on. The polygonal spiral path $P_1P_2P_3P_4P_5P_6P_7\ldots$ approaches a point $P$ inside the square.

a) If the coordinates of $P_n$ are $(x_n,y_n)$, show that $\frac{1}{2}x_n + x_{n+1} + x_{n+2} + x_{n+3} = 2$ and find a similar equation for the $y$-coordinates.

b) Find the coordinates of $P$.

-----

Remember to read the POTW submission guidelines to find out how to submit your answers!

 

[Chris L T521]

This week's problem was correctly answered by MarkFL. You can find his answer below.

Spoiler

Let's generalize a little to use a rectangle of base $b$ and height $h$ instead of a unit square, hence:

\(\displaystyle P_1=(0,h),\,P_2=(b,h),\,P_3=(b,0),\,P_4=(0,0)\)

a) We see that both $x_n$ and $y_n$ may be found using the recursive algorithm:

\(\displaystyle u_{n+4}\equiv\frac{u_{n}+u_{n+1}}{2}\)

This follows from the mid-point formula. Now, for such an algorithm, consider the following sum:

\(\displaystyle u_{n+4}+2u_{n+5}+2u_{n+6}+2_{n+7}=k\)

Using the algorithm, we have the following:

\(\displaystyle u_{n+4}+u_{n+1}+u_{n+2}+u_{n+2}+u_{n+3}+u_{n+3}+u_{n+4}=k\)

Collecting like terms, we find:

\(\displaystyle u_{n+1}+2u_{n+2}+2u_{n+3}+2u_{n+4}=k\)

From this, we may therefore conclude that for any $n$, we have:

\(\displaystyle u_{n}+2u_{n+1}+2u_{n+2}+2u_{n+3}=k\)

Where the parameter $k$ may be determined from the first 4 values of the sequence.

For the sequence $x_{n}$, we find:

\(\displaystyle x_{1}+2x_{2}+2x_{3}+2x_{4}=4b\implies \frac{1}{2}x_{n}+x_{n+1}+x_{n+2}+x_{n+3}=2b\)

For the sequence $y_n$, we find:

\(\displaystyle y_{1}+2y_{2}+2y_{3}+2y_{4}=3h\implies \frac{1}{2}y_{n}+y_{n+1}+y_{n+2}+y_{n+3}=\frac{3h}{2}\)

Using the data given for this problem:

\(\displaystyle b=h=1\)

we have:

\(\displaystyle \frac{1}{2}x_{n}+x_{n+1}+x_{n+2}+x_{n+3}=2\)

\(\displaystyle \frac{1}{2}y_{n}+y_{n+1}+y_{n+2}+y_{n+3}=\frac{3}{2}\)

b) Since the coordinates are converging to one value, namely $P(x,y)$, we may write:

\(\displaystyle x+2x+2x+2x=7x=4b\implies x=\frac{4b}{7}\)

\(\displaystyle y+2y+2y+2y=7y=3h\implies y=\frac{3h}{7}\)

Hence:

\(\displaystyle P(x,y)=\left(\frac{4b}{7},\frac{3h}{7} \right)\)

Using the data given for this problem:

\(\displaystyle b=h=1\)

we have:

\(\displaystyle P(x,y)=\left(\frac{4}{7},\frac{3}{7} \right)\)

edit by MarkFL (with permission given by Chris L T521):

The question about convergence of the sequence was brought up by one of our members. You can find the proof of convergence below:

Spoiler

Consider the linear homogenous recurrence obtained from the mid-point formula:

\(\displaystyle u_{n+4}=\frac{u_{n}+u_{n+1}}{2}\)

We may write this as:

\(\displaystyle 2u_{n+4}=u_{n+1}+u_{n}\)

From which, we obtain the characteristic polynomial:

\(\displaystyle 2r^4-r-1=(r-1)\left(2r^3+2r^2+2r+1 \right)=0\)

The characteristic roots, the irrational of which I will approximate, are given by:

\(\displaystyle r\approx1,\,-0.647798871261042,\, -0.176100564369479\pm0.860716618623568i\)

Hence, the closed form can be approximated with:

\(\displaystyle u_{n}\approx k_1+k_2(-0.647798871261042)^n+k_3(0.878546815113479)^n \sin\left(n\theta+k_4 \right)\)

We see then that we must have:

\(\displaystyle \lim_{n\to\infty}u_{n}=k_1\)

That is, the sequence $u_{n}$ must converge to some fixed value.