# 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, 6 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:

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, 6 months ago

Very interessting practice!

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

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

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

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

- 1 year, 6 months ago

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

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

Ah, okay.

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