Just an "Average" Proof

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

Start with a sequence \(a_n=\frac{a_{n-1}+a_{n-2}}{2}\), where the each term is the average of the previous terms. Define a function \(f\) that chooses the base terms, \(a_1\) and \(a_2\),: \[f(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.)\):

If \(f(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)=\frac{x+2y}{3}\).

It is interesting to note that the proposed function is the average of the numbers \(x,~y,\) and \(y\). 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,~\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 \(\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 \(y\)-coefficient in the \(n\)th term is the \(x\)-coefficient in the \(n-1\)th term (looking at the Python program shows why this is true).

Next, find the recursive formula for the \(y\)-coefficient of the \(n\)th term. Work: \[\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 \(\frac{2}{2}\), and then combine like terms. The new \(y\)-coefficient is the sum of the previous coefficient, double the coefficient before that, and 1. In other words, \(c_n=c_{n-1}+2c_{n-2}+1\), with \(c_1=c_2=0\).

Since the denominator of the \(n\)th term is \(2^{n-3}\), that means \[(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 \(y\)-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 \(\displaystyle\lim_{n\rightarrow \infty} \frac{c_n}{2^{n-3}}=L\). Secondly, it must be acknowledged that the \(x\)-coefficient is, as established earlier, \(c_{n-1}\). Therefore, the \(x\)-coefficient limit is \[\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 \(y\)-limit is the same as ignoring the \(x\) value of the function and plugging in 1 for \(y\) (since 1 is the multiplicative identity); the opposite is true for the \(x\)-limit. Therefore, the sum of these to limits is the output of the function when \(x=y=1\):

\[\implies L+\frac{L}{2}=f(1,~1)\]

Recall that \(f\) was the limit of a recurring sequence that averaged 2 terms. Consider \(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+\frac{L}{2}=f(1,~1)=1\] \[\frac{3}{2}L=1\] \[L=\frac{2}{3}\] Therefore, by \((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. 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.

Note by Blan Morrison
5 days, 4 hours ago

No vote yet
1 vote

  Easy Math Editor

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 \times 3 \)
2^{34} \( 2^{34} \)
a_{i-1} \( a_{i-1} \)
\frac{2}{3} \( \frac{2}{3} \)
\sqrt{2} \( \sqrt{2} \)
\sum_{i=1}^3 \( \sum_{i=1}^3 \)
\sin \theta \( \sin \theta \)
\boxed{123} \( \boxed{123} \)

Comments

Sort by:

Top Newest

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 \(\displaystyle a_n=\frac{a_{n-1}+a_{n-2}}{2}\) to:

\[\begin{align*} b_n&=a_{n-1} \\ a_n&=\frac{a_{n-1}+b_{n-1}}{2} \end{align*}\]

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

\[\begin{align*} \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{align*}\]

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

We can diagonalise the matrix \(A\) using its eigenvalues and eigenvectors. For this question,

\[A = 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 \(A^n\):

\[A^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 \(a_n\) diverges. If it does, the terms in \(Q^n\) would blow up, making \(A^n \vec x\) blow up as well. Luckily, (and expectedly), for this value of \(A\), the terms in Q converge, making:

\[\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:

\[\begin{align*}\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{align*}\]

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

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

Julian Poon - 1 day, 20 hours ago

Log in to reply

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

On a more sour note: Can you check your calculations again? The matrix \(A\) should read

\( \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 \(a_0\) and \(a_1\) instead of \(a_1\) and \(a_2\) then you would want the matrix equation to start at \(n = 1\), so that your initial terms are given by \(b_1\) and \(a_1\), not \(b_0\) and \(a_0\). Aside from that, maybe you could check your SVD again, but it shouldn't change the \(Q\) matrix if you modify the \(P\) matrix. I'd also put a \(\lim\) sign in front of the \(b_n\), \(a_n\) vector at the end, to be precise.

Gennady Notowidigdo - 4 hours ago

Log in to reply

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

Julian Poon - an hour ago

Log in to reply

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

Gennady Notowidigdo - 43 minutes ago

Log in to reply

I'm confused when you say "generalize." Do you mean the average of the previous \(n\) 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 - 23 hours ago

Log in to reply

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

Gennady Notowidigdo - 5 hours ago

Log in to reply

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

Julian Poon - 22 hours ago

Log in to reply

@Julian Poon Ah, okay.

Blan Morrison - 14 hours ago

Log in to reply

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

Gennady Notowidigdo - 4 days, 20 hours 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 - 4 days, 14 hours ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...