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

Note by Blan Morrison
1 year, 2 months ago

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.

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:

Reproductive toxicology is one of the most complicated areas of toxicology research due to the involvement of multiple organs and tissues, different modes of toxicant action and dependence on the endocrine system. In particular, endocrine disrupters represent a significant challenge for experimental toxicology because of their complex effects on signal networks and programming.

https://www.creative-bioarray.com/dda-platform/reproductive-toxicology.html

- 3 months, 1 week ago

One afterthought: generalization.

Others have considered the same idea, but I'm specifically generalizing where $a_n$ is the average of the previous $k$ terms and $f$ has $k$ inputs. I edited my Python code I used in the proof to fit $k=3$, and I successfully predicted multiple outputs with the function $f(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 $k$, but I conjecture

If $a_n$ is the average of the previous $k$ terms and $f$ has $k$ inputs, then $f(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}$

- 1 year, 2 months ago

Very interessting practice!

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

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

\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 $\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{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, $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 year, 2 months 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.

- 1 year, 2 months 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

- 1 year, 2 months ago

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

- 1 year, 2 months 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).

- 1 year, 2 months ago

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

- 1 year, 2 months ago

I saw that wiki, but thank you for pointing that out. Also, thanks for helping with Julian's generalization.

- 1 year, 2 months ago

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

- 1 year, 2 months ago

Ah, okay.

- 1 year, 2 months 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...

- 1 year, 2 months ago

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

- 1 year, 2 months ago