# 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

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. 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 1paragraph 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}$$

Sort by:

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.

- 1 day, 20 hours ago

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.

- 4 hours ago

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

- an hour ago

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

- 43 minutes ago

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).

- 23 hours ago

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

- 5 hours ago

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

- 22 hours ago

Ah, okay.

- 14 hours ago

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...

- 4 days, 20 hours ago

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

- 4 days, 14 hours ago