Just an "Average" Proof

I honestly have no idea how this problem came to mind. Oh well; here it goes.

Start with a sequence an=an−1+an−22a_n=\frac{a_{n-1}+a_{n-2}}{2}, where the each term is the average of the previous terms. Define a function ff that chooses the base terms, a1a_1 and a2a_2,: f(x, y)={x=a1y=a2an=an−1+an−22lim⁡n→∞anf(x,~y)=\begin{cases} x=a_1 \\ y=a_2 \\ a_n=\frac{a_{n-1}+a_{n-2}}{2} \\ \displaystyle\lim_{n\rightarrow \infty}a_n \end{cases}

After coding up the function in Python and testing a few cases, I conjectured (i.)(i.):

If f(x, y)={x=a1y=a2an=an−1+an−22lim⁡n→∞anf(x,~y)=\begin{cases} x=a_1 \\ y=a_2 \\ a_n=\frac{a_{n-1}+a_{n-2}}{2} \\ \displaystyle\lim_{n\rightarrow \infty}a_n \end{cases}, then f(x, y)=x+2y3f(x,~y)=\frac{x+2y}{3}.

It is interesting to note that the proposed function is the average of the numbers x, y,x,~y, and yy. While it seems pretty obvious that this is true, nothing is true in mathematics until it is proven. A proof by induction probably seems like the most logical method, but I don't really know how to perform such a proof, much less with 2 variables. So, I tried deriving the formula.

Start with the first few terms of the sequence: x, y, x+y2, x+y2+y2, x+y2+x+2y4, x+y2+2x+5y8,…x,~y,~\frac{x+y}{2},~\frac{\frac{x+y}{2}+y}{2},~\frac{\frac{x+y}{2}+x+2y}{4},~\frac{\frac{x+y}{2}+2x+5y}{8},\dots A pattern is most definitely emerging:

  1. The third term (x+y2)\left(\frac{x+y}{2}\right) is always present in the sequence.

  2. The denominator seems to be increasing in powers of 2 (the algebra shows why).

  3. The yy-coefficient in the nnth term is the xx-coefficient in the n+1n+1th term (looking at the Python program shows why this is true).

Next, find the recursive formula for the yy-coefficient of the nnth term. Work: x+y2+x+2y4+x+y2+2x+5y82=x+y+2x+4y+x+y2+2x+5y82=x+y2+5x+10y16\dfrac{\dfrac{\frac{x+y}{2}+x+2y}{4}+\dfrac{\frac{x+y}{2}+2x+5y}{8}}{2}=\dfrac{\dfrac{x+y+2x+4y+\frac{x+y}{2}+2x+5y}{8}}{2}=\dfrac{\frac{x+y}{2}+5x+10y}{16}

Firstly, multiply first term by 22\frac{2}{2}, and then combine like terms. The new yy-coefficient is the sum of the previous coefficient, double the coefficient before that, and 1. In other words, cn=cn−1+2cn−2+1c_n=c_{n-1}+2c_{n-2}+1, with c1=c2=0c_1=c_2=0.

Since the denominator of the nnth term is 2n−32^{n-3}, that means (ii.) f(x, y)=x+2y3  ⟺  lim⁡n→∞cn2n−3=23(ii.)~f(x,~y)=\frac{x+2y}{3}\iff \displaystyle\lim_{n\rightarrow \infty}\frac{c_n}{2^{n-3}}=\frac{2}{3} In other words, in order for the function to be true, the yy-coefficient in the algebraic expansion needs to be two-thirds of the denominator as the order of terms gets larger. (This is the link that can prove the function!)

Firstly, define lim⁡n→∞cn2n−3=L\displaystyle\lim_{n\rightarrow \infty} \frac{c_n}{2^{n-3}}=L. Secondly, it must be acknowledged that the xx-coefficient is, as established earlier, cn−1c_{n-1}. Therefore, the xx-coefficient limit is lim⁡n→∞cn−12n−3=lim⁡n→∞cn2n−2=lim⁡n→∞cn2n−3⋅2=L2\displaystyle\lim_{n\rightarrow \infty} \frac{c_{n-1}}{2^{n-3}}=\displaystyle\lim_{n\rightarrow \infty} \frac{c_n}{2^{n-2}}=\displaystyle\lim_{n\rightarrow \infty} \frac{c_n}{2^{n-3}\cdot 2}=\frac{L}{2}

Next, find the sum of these two limits; the yy-limit is the same as ignoring the xx value of the function and plugging in 1 for yy (since 1 is the multiplicative identity); the opposite is true for the xx-limit. Therefore, the sum of these to limits is the output of the function when x=y=1x=y=1:

  ⟹  L+L2=f(1, 1)\implies L+\frac{L}{2}=f(1,~1)

Recall that ff was the limit of a recurring sequence that averaged 2 terms. Consider f(b, b)f(b,~b): taking the average of 2 identical numbers outputs that number. If the process is repeated infinitely many times, it will make no difference. Therefore, L+L2=f(1, 1)=1L+\frac{L}{2}=f(1,~1)=1 32L=1\frac{3}{2}L=1 L=23L=\frac{2}{3} Therefore, by (ii.)(ii.), the original conjecture is true!

β⌈∣⌉\huge{\beta_{\lceil \mid \rceil}}

Please feel free to critique this proof; I am here to learn! I feel that it is too unprofessional, but I am still proud of it; after writing the proof, I googled "recursive sequence limits" and found a much shorter proof on StackExchange, so I know this isn't the best possible proof. I feel like such an amateur after writing this because it is so informal, and I wonder if this what being a "real" mathematician is like. Of course, it probably isn't and I'm just being a kid with excessively high hopes.

#Algebra

Note by Blan Morrison
2 years, 7 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list
  • bulleted
  • list

1. numbered
2. list
  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai−1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 ∑i=13 \sum_{i=1}^3
\sin \theta sin⁡θ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

A really interesting note! Have you thought about generalising what happens with this sequence for an nthn^{\text{th}}-order linear recurrence relations? Would be interesting to see what happens...

A Former Brilliant Member - 2 years, 7 months ago

Log in to reply

I was just thinking about that this morning! I'll definitely make an update about that sometime in the next 12 hours.

Blan Morrison - 2 years, 7 months ago

Interesting! If you add in a little linear algebra, you would be able to generalise to more linear recurrence relations of higher order, and even know whether it converges at all:

You can split your recurrence relation into multiple degree 1 recurrence relations. For your recurrence this goes from an=an−1+an−22\displaystyle a_n=\frac{a_{n-1}+a_{n-2}}{2} to:

bn=an−1an=an−1+bn−12\begin{aligned} b_n&=a_{n-1} \\ a_n&=\frac{a_{n-1}+b_{n-1}}{2} \end{aligned}

The reason for doing this is so that you can express the nth term of the recurrence relation as a matrix product:

(a0b0)=(yx)(anbn)=(0.50.510)n(yx)\begin{aligned} \begin{pmatrix} a_0 \\ b_0 \end{pmatrix} &= \begin{pmatrix} y \\ x \end{pmatrix} \\ \begin{pmatrix} a_n \\ b_n\end{pmatrix} &= \begin{pmatrix} 0.5 & 0.5 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} y \\ x \end{pmatrix} \end{aligned}

Let's make (0.50.510)=A\displaystyle \begin{pmatrix} 0.5 & 0.5 \\ 1 & 0 \end{pmatrix} = A and (yx)=x⃗\displaystyle \begin{pmatrix} y \\ x \end{pmatrix} = \vec x for notation sake. If we want to find ana_n as n→∞n \rightarrow \infty, then we want to find lim⁡n→∞Anx⃗ \displaystyle \lim_{n \rightarrow \infty} A^n \vec x

We can diagonalise the matrix AA using its eigenvalues and eigenvectors. For this question,

A=PQP−1=(1−0.511)(100−0.5)(1−0.511)−1A = PQP^{-1} = \begin{pmatrix} 1 & -0.5 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & -0.5 \end{pmatrix} \begin{pmatrix} 1 & -0.5 \\ 1 & 1 \end{pmatrix}^{-1}

And the reason why we diagonalise it is because we can easily calculate AnA^n:

An=PQnP−1=(1−0.511)(1n00(−0.5)n)(1−0.511)−1A^n = PQ^nP^{-1} = \begin{pmatrix} 1 & -0.5 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} 1^n & 0 \\ 0 & (-0.5)^n \end{pmatrix} \begin{pmatrix} 1 & -0.5 \\ 1 & 1 \end{pmatrix}^{-1}

It is here we can see if ana_n diverges. If it does, the terms in QnQ^n would blow up, making Anx⃗A^n \vec x blow up as well. Luckily, (and expectedly), for this value of AA, the terms in Q converge, making:

lim⁡n→∞An=(1−0.511)(1000)(1−0.511)−1\lim_{n\rightarrow \infty} A^n = \begin{pmatrix} 1 & -0.5 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} \begin{pmatrix} 1 & -0.5 \\ 1 & 1 \end{pmatrix}^{-1}

And so the coveted value we wanna find can be calculated by:

(anbn)=(11−0.51)(1000)(11−0.51)−1(yx)=13(2x+y2x+y)\begin{aligned}\begin{pmatrix} a_n \\ b_n\end{pmatrix} &= \begin{pmatrix} 1 & 1 \\ -0.5 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ -0.5 & 1 \end{pmatrix}^{-1} \begin{pmatrix} y \\ x \end{pmatrix} \\ &= \frac{1}{3} \begin{pmatrix} 2x+y \\ 2x+y \end{pmatrix} \end{aligned}

Interestingly, in general, ana_n is likely to diverge or go to 0. This is because in order for ana_n to converge to a non-zero value, QQ must have an entry of value 11, or QnQ^n diverges or becomes the null matrix. You are very lucky to have chanced upon this recurrence relation.

Oh and as for the LaTeX\LaTeX, you can use \begin{align} <ur eqns> \end{align} to line them up neatly.

Julian Poon - 2 years, 7 months ago

Log in to reply

I'm confused when you say "generalize." Do you mean the average of the previous nn terms instead of 2? It looked to me as if you did something different, but I honestly have little to no comprehension of linear algebra (yet).

Blan Morrison - 2 years, 7 months ago

Log in to reply

By generalise I mean any recurrence relation of the form an=∑i=1kcian−i \displaystyle a_n = \sum_{i=1}^{k} c_i a_{n-i}

Julian Poon - 2 years, 7 months ago

Log in to reply

@Julian Poon – Ah, okay.

Blan Morrison - 2 years, 7 months ago

Have a look into linear recurrence relations and how to solve them in general.

A Former Brilliant Member - 2 years, 7 months ago

Log in to reply

@A Former Brilliant Member – I saw that wiki, but thank you for pointing that out. Also, thanks for helping with Julian's generalization.

Blan Morrison - 2 years, 7 months ago

To add to the last point: You'd want the eigenvalues of QQ to all be between −1-1 and 11 (inclusive, I think?), otherwise the limit of the SVD approaches infinity.

On a more sour note: Can you check your calculations again? The matrix AA should read

(010.50.5) \begin{pmatrix} 0 & 1 \\ 0.5 & 0.5 \end{pmatrix}

if you define the recurrence as such. If we modify Blan's initial terms to a0a_0 and a1a_1 instead of a1a_1 and a2a_2 then you would want the matrix equation to start at n=1n = 1, so that your initial terms are given by b1b_1 and a1a_1, not b0b_0 and a0a_0. Aside from that, maybe you could check your SVD again, but it shouldn't change the QQ matrix if you modify the PP matrix. I'd also put a lim⁡\lim sign in front of the bnb_n, ana_n vector at the end, to be precise.

A Former Brilliant Member - 2 years, 7 months ago

Log in to reply

My bad, this can be easily remedied by switching the positions of ana_n and bnb_n, a typo on my part. If we want ana_n to converge to a finite non zero value, all the entries of QQ have to be between -1 and 1, inclusive of 11 but not inclusive of −1-1. Furthermore, at least 1 entry of QQ has to be 11. With regards to the undex starting from 00, it is essentially the same, but i chose to start from 0 so that I don't have a n+1n+1 power in my QQ, which is kinda ugly

Julian Poon - 2 years, 7 months ago

Log in to reply

@Julian Poon – No worries. Just wanted to make sure your notation is consistent with Blan’s.

A Former Brilliant Member - 2 years, 7 months ago

Very interessting practice!

Anton Goetze - 2 years, 7 months ago

One afterthought: generalization.

Others have considered the same idea, but I'm specifically generalizing where ana_n is the average of the previous kk terms and ff has kk inputs. I edited my Python code I used in the proof to fit k=3k=3, and I successfully predicted multiple outputs with the function f(x, y, z)=x+2y+3z6f(x,~y,~z)=\frac{x+2y+3z}{6}.

I currently don't have the time (and quite possibly the ability, but I'll try later) to prove the general case for kk, but I conjecture

If ana_n is the average of the previous kk terms and ff has kk inputs, then f(x1, x2, … xk−1, xk)=∑i=1kixi∑i=1ki=2⋅∑i=1kixik2+kf(x_1,~x_2,~\dots ~x_{k-1},~x_k)=\frac{\displaystyle\sum_{i=1}^{k}ix_i}{\displaystyle\sum_{i=1}^{k}i}=2\cdot \dfrac{\displaystyle\sum_{i=1}^{k}ix_i}{k^2+k}

Blan Morrison - 2 years, 7 months ago
×

Problem Loading...

Note Loading...

Set Loading...