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:

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

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

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.

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

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

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.

Log in to reply

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.

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

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} \)

Log in to reply

Log in to reply

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

Log in to reply

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.

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

Log in to reply

Log in to reply

Very interessting practice!

Log in to reply

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

Log in to reply