# Math help: limit of a self-referential equation

**URL:** <https://boards.straightdope.com/t/math-help-limit-of-a-self-referential-equation/548415>\
**Category:** Factual Questions\
**Created:** [July 29, 2010, 3:40am UTC](https://boards.straightdope.com/t/math-help-limit-of-a-self-referential-equation/548415 "2010-07-29T03:40:08Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![BigT](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/bigt/32/12044_2.png) [@BigT](https://boards.straightdope.com/u/BigT)\
**Post date:** [July 29, 2010, 3:40am UTC](https://boards.straightdope.com/t/math-help-limit-of-a-self-referential-equation/548415/1 "2010-07-29T03:40:08Z")

</div>

I have a formula for certain self referential equations all of the form:  
f[sub]n[/sub] = f[sub]n-1[/sub] \* 2[sup]-xn[/sup] + 1 ; f[sub]0[/sub] = 0

I solved it for x = 1 by just plugging it in and noticing the pattern. f’[sub]n[/sub] = 2 - 2[sup]-n[/sup], and realized that the limit as n approaches infinity would therefore be just plain 2.

However, when I used x = 2/3, I had no idea what to do, and wrote a program (JavaScript in the spoiler) to figure out the answer. The limit is 2.702414383919315 to the precision my program can handle.

But I have no idea how to approach said equations (and finding their infinite limits) without having to use such a “brute force” method. Can you help?

```php
x = 1.0;
y = 1.0;
do { 
    x = y
    y = Math.exp(2,2/3) + 1.0 
} while (x != y);
window.prompt("x =",x);

```

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [July 29, 2010, 3:45am UTC](https://boards.straightdope.com/t/math-help-limit-of-a-self-referential-equation/548415/2 "2010-07-29T03:45:41Z")

</div>

> [@BigT](#):
>
> We’ll start with the **math question** :

Is there a non-math question as well?

> [@](#):
>
> I have a formula for certain self referential equations all of the form:  
> f[sub]n[/sub] = f[sub]n-1[/sub] \* 2[sup]-xn[/sup] + 1 ; f[sub]0[/sub] = 0

Your code indicates that you meant to write 2[sup]-x[/sup] rather than 2[sup]-xn[/sup]. Is that correct?

Whenever you have a series defined by f[sub]n+1[/sub] = g(f[sub]n[/sub]) for some continuous function g, and L is the limit of f[sub]n[/sub] as n approaches infinity, then L = g(L). Accordingly, in this case, if said limit exists, then L = L \* 2[sup]-x[/sup] + 1, which is to say, L = -1/(2[sup]-x[/sup] - 1).

Actually proving that there is a limit is often a separate matter. In this case, the series will converge to the limit so long as |2[sup]-x[/sup]| \< 1 (plus, in a sense, the series will also approach its limit of infinity when 2[sup]-x[/sup] = 1).

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [July 29, 2010, 3:57am UTC](https://boards.straightdope.com/t/math-help-limit-of-a-self-referential-equation/548415/3 "2010-07-29T03:57:55Z")

</div>

Let k = 2[sup]-x[/sup], to make my life easier. The reason for the convergence is that more explicitly, f[sub]n[/sub] = 1 + k + k[sup]2[/sup] + … + k[sup]n-1[/sup] = (1 - k[sup]n[/sup])/(1 - k). As n goes to infinity, what happens to |k[sup]n[/sup]| is one of three things: it goes to 0 if |k| \< 1, it goes to infinity if |k| \> 1, and it stays equal to 1 if |k| = 1 (in this case, k[sup]n[/sup] keeps rotating through the unit circle in the complex plane if k is not 1, and stays fixed at 1 if k is 1).

[In this case, the method we used to prove convergence could easily be used to establish the value of the limit itself; but, as I said, they are often a separate matter, even if not always]

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [July 29, 2010, 4:05am UTC](https://boards.straightdope.com/t/math-help-limit-of-a-self-referential-equation/548415/4 "2010-07-29T04:05:02Z")

</div>

[Perhaps a useful alternative way of writing the limit, depending on what you’re doing: 2[sup]x[/sup]/(2[sup]x[/sup] - 1), with convergence just in case x \> 0. But these are trivial reformattings…]

---

<div class="post-metadata">

**Author:** ![BigT](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/bigt/32/12044_2.png) [@BigT](https://boards.straightdope.com/u/BigT)\
**Post date:** [July 29, 2010, 10:05am UTC](https://boards.straightdope.com/t/math-help-limit-of-a-self-referential-equation/548415/5 "2010-07-29T10:05:18Z")

</div>

Yes, I did write the exponent incorrectly.

I think my problem is getting from f[sub]n[/sub] = 1 + k + k[sup]2[/sup] + … + k[sup]n-1[/sup] to f[sub]n[/sub] = (1 - k[sup]n[/sup])/(1 - k). And not realizing that the pattern would hold from what I observed with x = 1. I only knew that from my work in binary, adding subsequent powers of two would lead you to the next power minus one, and thus adding subsequent powers of 1/2 would equal one. For some reason I was unable to generalize 1/2 into k and create an equation.

Of course, a lot of what you said took a while for me to get, so I don’t know if explaining how both f functions are equivalent would be something I could grasp. The math part of my brain seems to have atrophied, and thinking too much literally gives me headaches now.

I do at least get how to get to lim[sub]n-\>∞[/sub] f[sub]n[/sub] = 2[sup]x[/sup]/(2[sup]x[/sup] - 1). You multiply by 2[sup]x[/sup]/2[sup]x[/sup].

BTW, do you know a better term for these types of equations? That’s why my title is incomplete–I couldn’t think of the term.

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [July 29, 2010, 10:22am UTC](https://boards.straightdope.com/t/math-help-limit-of-a-self-referential-equation/548415/6 "2010-07-29T10:22:21Z")

</div>

The reason 1 + k + k[sup]2[/sup] + … + k[sup]n - 1[/sup] = (1 - k[sup]n[/sup])/(1 - k) is because (1 - k) \* (1 + k + k[sup]2[/sup] + … + k[sup]n - 1[/sup]) = 1 \* (1 + k + k[sup]2[/sup] + … + k[sup]n - 1[/sup]) - k \* (1 + k + k[sup]2[/sup] + … + k[sup]n - 1[/sup]) = 1 + k + k[sup]2[/sup] + … + k[sup]n - 1[/sup] - k - k[sup]2[/sup] - k[sup]3[/sup] - … - k[sup]n[/sup] = 1 - k[sup]n[/sup].

Series in which each term is defined by some function applied to previous terms are said to be defined by “recurrence relations”; is that what you mean by “these types of equations”?

---

<div class="post-metadata">

**Author:** ![BigT](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/bigt/32/12044_2.png) [@BigT](https://boards.straightdope.com/u/BigT)\
**Post date:** [July 29, 2010, 11:44am UTC](https://boards.straightdope.com/t/math-help-limit-of-a-self-referential-equation/548415/7 "2010-07-29T11:44:46Z")

</div>

I see. That was a lot easier than I thought. And, I don’t know if that’s the term my textbook used back in the day, but that is what I was asking. Before I made the post, I tried my best to find out a proper term for those relations.

If you care, my original second question was a problem I was having with the JavaScript. Apparently the ^ does not mean exponentiation, but also does not produce an error.

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [July 29, 2010, 3:11pm UTC](https://boards.straightdope.com/t/math-help-limit-of-a-self-referential-equation/548415/8 "2010-07-29T15:11:39Z")

</div>

The ^ probably means bitwise XOR.

---

<div class="post-metadata">

**Author:** ![Gary\_Robson](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/gary_robson/32/3448_2.png) [@Gary\_Robson](https://boards.straightdope.com/u/Gary_Robson)\
**Post date:** [July 29, 2010, 9:31pm UTC](https://boards.straightdope.com/t/math-help-limit-of-a-self-referential-equation/548415/9 "2010-07-29T21:31:34Z")

</div>

[moderating]  
Thread title changed from “limit of” to “Math help: limit of a self-referential equation” at the OP’s request.  
[/moderating]

---

<div class="post-metadata">

**Author:** ![BigT](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/bigt/32/12044_2.png) [@BigT](https://boards.straightdope.com/u/BigT)\
**Post date:** [August 3, 2010, 7:38am UTC](https://boards.straightdope.com/t/math-help-limit-of-a-self-referential-equation/548415/10 "2010-08-03T07:38:04Z")

</div>

Hey! Just realized I didn’t thank you, **Indistinguishable**. Man, you were on this like a \<funny Southern thing\> on \<something else\>.