Arithmetic and Geometric Series: Index

I’m using the Twelve Days of Christmas (and perhaps a few extra days besides) to do something that I should have done a long time ago: collect past series of posts into a single, easy-to-reference post. The following posts formed my series on how I remind students about Taylor series. I often use this series in a class like Differential Equations, when Taylor series are needed but my class has simply forgotten about what a Taylor series is and why it’s important.

Part 1: Deriving the formulas for the nth term of arithmetic and geometric sequences.

Part 2: Pedagogical thoughts on conceptual barriers that students often face when encountering sequences and series.

Part 3: The story of how young Carl Frederich Gauss, at age 10, figured out how to add the integers from 1 to 100 in his head.

Part 4: Deriving the formula for an arithmetic series.

Part 5: Deriving the formula for an arithmetic series, using mathematical induction. Also, extensions to other series.

Part 6: Deriving the formula for an arithmetic series, using telescoping series. Also, extensions to other series.

Part 7: Pedagogical thoughts on assessing students’ depth of understanding the formula for an arithmetic series.

Part 8: Deriving the formula for a finite geometric series.

Part 9: Infinite geometric series and Xeno’s paradox.

Part 10: Deriving the formula for an infinite geometric series.

Part 11: Applications of infinite geometric series in future mathematics courses.

Part 12: Other commonly-arising infinite series.

 

 

 

2048 and algebra: Index

I’m doing something that I should have done a long time ago: collect past series of posts into a single, easy-to-reference post. The following posts formed my series on using algebra to study the 2048 game… with a special focus on reaching the event horizon of 2048 which cannot be surpassed.

2048-0Part 1: Introduction and statement of problem

Part 2: First insight: How points are accumulated in 2048

Part 3: Second insight: The sum of the tiles on the board

Part 4: Algebraic formulation of the two insights

Part 5: Algebraic formulation applied to a more complicated board

Part 6: Algebraic formulation applied to the event horizon of 2048

Part 7: Calculating one of the complicated sums in Part 6 using a finite geometric series

Part 8: Calculating another complicated sum in Part 6 using a finite geometric series

Part 9: Repeating Part 8 by reversing the order of summation in a double sum

Part 10: Estimating the probability of reaching the event horizon in game mode

 

 

 

 

2048 and algebra (Part 9)

In this series of posts, I consider how algebra can be used to answer a question about the 2048 game: From looking at a screenshot of the final board, can I figure out how many moves were needed to reach the final board? Can I calculate how many new 2-tiles and 4-tiles were introduced to the board throughout the course of this game? In this post, we consider the event horizon of 2048, which I reached after about four weeks of intermittent doodling:

2048-0

In yesterday’s post, we developed a system of two equations in two unknowns to solve for t and f, the number of 2-tiles and 4-tiles (respectively) that appeared throughout the course of the game:

2t + 4f = \displaystyle \sum_{n=2}^{17} 2^n.

2t + \displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = 3,867,072

In this post and tomorrow’s post, I consider how the two sums in the above equations can be obtained without directly adding the terms.

In yesterday’s post, we used the formula for the sum of a finite geometric series to calculate the second sum:

\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = 14 \times 2^{18} + 2^3 = 3,670,024

In this post, I perform this calculation again, except symbolically and more compactly. The key initial steps are writing the series as a double sum and then interchanging the order of summation (much like reversing the order of integration in a double integral). This is a trick that I’ve used again and again in my own research efforts, but it seems that the students that I teach have never learned this trick. Here we go:

\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = \displaystyle \sum_{n=1}^{15} \sum_{k=1}^n 2^{n+2} = \displaystyle \sum_{k=1}^{15} \sum_{n=k}^{15} 2^{n+2}

The inner sum is a finite geometric series with 15-k+1 terms, common ratio of 2, and initial term 2^{k+2}. Therefore,

\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = \displaystyle \sum_{k=1}^{15} \frac{ 2^{k+2} \left(1 - 2^{15-k+1} \right) }{1 - 2}

= \displaystyle \sum_{k=1}^{15} \left(2^{18} - 2^{k+2} \right)

= \displaystyle \sum_{k=1}^{15} 2^{18} -\sum_{k=1}^{15} 2^{k+2}

 The first sum is merely the sum of a constant. The second sum is another finite geometric series with 15 terms, common ratio of 2, and initial term 2^3. So

\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = 15 \times 2^{18} - \displaystyle \frac{ 2^3 \left(1 - 2^{15} \right) }{1 - 2}

\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = 15 \times 2^{18} - \left( 2^{18} - 2^3 \right)

\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = 14 \times 2^{18} + 2^3

\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = 3,670,024

2048 and algebra (Part 8)

In this series of posts, I consider how algebra can be used to answer a question about the 2048 game: From looking at a screenshot of the final board, can I figure out how many moves were needed to reach the final board? Can I calculate how many new 2-tiles and 4-tiles were introduced to the board throughout the course of this game? In this post, we consider the event horizon of 2048, which I reached after about four weeks of intermittent doodling:

2048-0

In yesterday’s post, we developed a system of two equations in two unknowns to solve for t and f, the number of 2-tiles and 4-tiles (respectively) that appeared throughout the course of the game:

2t + 4f = \displaystyle \sum_{n=2}^{17} 2^n.

2t + \displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = 3,867,072

In this post and tomorrow’s post, I consider how the two sums in the above equations can be obtained without directly adding the terms.

In yesterday’s post, we showed that the formula for the sum of a finite geometric series can be used to calculate the first sum:

\displaystyle \sum_{n=2}^{17} 2^n = \displaystyle \frac{4(1-2^{16})}{1-2} = 4(2^{15} - 1) = 262,140

Let’s now consider the second (and more complicated) sum, which can be written as

2^3 + 2 \cdot 2^4 + 3 \cdot 2^5 + \cdot + 15 \cdot 2^{17}

For reasons that will become clear shortly, this sum can be written in expanded form as

2^3

+ 2^4 + 2^4

+ 2^5 + 2^5 + 2^5

\vdots

+ 2^{17} + 2^{17} + 2^{17} + \dots + 2^{17}

 Let’s now rearrange the terms of this sum. We will do this by adding along the diagonals instead of along the rows. In this way, the above sum can be rearranged as

2^3 + 2^4 + 2^5 + \dots + 2^{17}

+ 2^4 + 2^5 + \dots + 2^{17}

+ 2^5 + \dots + 2^{17}

\vdots

+ 2^{17}

Each of these new rows (or the original diagonals) is a geometric series and can be calculated using the formula:

2^3 + 2^4 + 2^5 + \dots + 2^{17} = \displaystyle \frac{2^3 (1-2^{15})}{1-2} = 2^{18} - 2^3

2^4 + 2^5 + \dots + 2^{17} = \displaystyle \frac{2^4 (1-2^{14})}{1-2} = 2^{18} - 2^4

2^5 + \dots + 2^{17} = \displaystyle \frac{2^5 (1-2^{13})}{1-2} = 2^{18} - 2^5

\vdots

2^{17} = (2-1) \cdot 2^{17} = 2^{18} - 2^{17}

So, thus far in the calculation, we have established that

\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = \displaystyle \sum_{n=3}^{17} \left( 2^{18} - 2^n \right).

Simplifying,

\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2}=\displaystyle \sum_{n=3}^{17} 2^{18} - \sum_{n=3}^{17} 2^n

The first sum on the right is the sum of a constant being added to itself 15 times:

\displaystyle \sum_{n=3}^{17} 2^{18} = 15 \times 2^{18}

The second sum on the right is yet another geometric series. Indeed, it’s the same geometric  series from the first diagonal above:

\sum_{n=3}^{17} 2^n = \displaystyle \frac{2^3 (1-2^{15})}{1-2} = 2^{18} - 2^3

Therefore,

\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = 15 \times 2^{18} - \left(2^{18} - 2^3 \right)

\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = 14 \times 2^{18} + 2^3

\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = 3,670,024

Not surprisingly, this matches the sum that was found via direct addition.

2048 and algebra (Part 7)

In this series of posts, I consider how algebra can be used to answer a question about the 2048 game: From looking at a screenshot of the final board, can I figure out how many moves were needed to reach the final board? Can I calculate how many new 2-tiles and 4-tiles were introduced to the board throughout the course of this game? In this post, we consider the event horizon of 2048, which I reached after about four weeks of intermittent doodling:

2048-0

In yesterday’s post, we developed a system of two equations in two unknowns to solve for t and f, the number of 2-tiles and 4-tiles (respectively) that appeared throughout the course of the game:

2t + 4f = \displaystyle \sum_{n=2}^{17} 2^n.

2t + \displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = 3,867,072

In this post and tomorrow’s post, I consider how the two sums in the above equations can be obtained without directly adding the terms.

The first sum is certainly the easiest to handle, as it requires the sum of a finite geometric series:

a + ar + ar^2 + \dots + a r^{n-1} = \displaystyle \sum_{i=1}^n a r^{i-1} = \displaystyle \frac{a(1-r^n)}{1-r}

For the geometric series

\displaystyle \sum_{n=2}^{17} 2^n,

there are 16 terms (after all, there are 16 tiles on the board). The first term is 4, and the common ratio is 2. Therefore,

\displaystyle \sum_{n=2}^{17} 2^n = \displaystyle \frac{4(1-2^{16})}{1-2}

\displaystyle \sum_{n=2}^{17} 2^n = 4(2^{15} - 1)

\displaystyle \sum_{n=2}^{17} 2^n = 262,140

We’ll consider the more complicated sum in tomorrow’s post.

 

Exponential growth and decay (Part 6): Paying off credit-card debt via recurrence relations

The following problem in differential equations has a very practical application for anyone who has either (1) taken out a loan to buy a house or a car or (2) is trying to pay off credit card debt. To my surprise, most math majors haven’t thought through the obvious applications of exponential functions as a means of engaging their future students, even though it is directly pertinent to their lives (both the students’ and the teachers’).

You have a balance of $2,000 on your credit card. Interest is compounded continuously with a rate of growth of 25% per year. If you pay the minimum amount of $50 per month (or $600 per year), how long will it take for the balance to be paid?

In previous posts, I approached this problem using differential equations. There’s another way to approach this problem that avoids using calculus that, hypothetically, is within the grasp of talented Precalculus students. Instead of treating this problem as a differential equation, we instead treat it as a first-order difference equation (also called a recurrence relation):

A_{n+1} = r A_n - k

The idea is that the amount owed is multiplied by a factor r (which is greater than 1), and from this product the amount paid is deducted. With this approach — and unlike the approach using calculus — the payment period would be each month and not per year. Therefore, we can write

A_{n+1} = \displaystyle \left( 1 + \frac{0.25}{12} \right) A_n - 50

Notice that the meaning of the 25% has changed somewhat… it’s no longer the relative rate of growth, as the 25% has been equally divided for the 12 months.

green line

In yesterday’s post, I demonstrated that the solution of this recurrence relation is

A_n = r^n P - k \displaystyle \left( \frac{1 - r^n}{1-r} \right).

Let’s now study when the credit card debt will actually reach $0. To do this, we see A_n = 0 and solve for n:

0 = r^n P - k \displaystyle \left( \frac{1 - r^n}{1-r} \right)

0 = r^n \left(P + \displaystyle \frac{k}{1-r} \right) - \displaystyle \frac{k}{1-r}

0 = r^n \left( P[1-r] + k \right) - k

k = r^n \left( P[1-r] + k \right)

\displaystyle \frac{k}{P[1-r] + k} = r^n

\displaystyle \ln \left( \frac{k}{P[1-r]+k} \right) = n \ln r

\displaystyle \frac{ \displaystyle \ln \left( \frac{k}{P[1-r]+k} \right) }{ \ln r} = n

That’s certainly a mouthful. However, this calculation should be accessible to a talented student in Precalculus.

Let’s try it out for k = 50, P = 2000, and r = 1 + \displaystyle \frac{0.25}{12}:

recurrencecreditcard

Remembering that each compounding period is one month long, this corresponds to 86.897/12 \approx 7.24 years, which is nearly equal to the value of 4\ln 6 \approx 7.17 years when we solved this problem using differential equations under the assumption of continuous compound interest (as opposed to interest that’s compoounded monthly).

Exponential growth and decay (Part 5): Paying off credit-card debt via recurrence relations

The following problem in differential equations has a very practical application for anyone who has either (1) taken out a loan to buy a house or a car or (2) is trying to pay off credit card debt. To my surprise, most math majors haven’t thought through the obvious applications of exponential functions as a means of engaging their future students, even though it is directly pertinent to their lives (both the students’ and the teachers’).

You have a balance of $2,000 on your credit card. Interest is compounded continuously with a rate of growth of 25% per year. If you pay the minimum amount of $50 per month (or $600 per year), how long will it take for the balance to be paid?

In previous posts, I approached this problem using differential equations. There’s another way to approach this problem that avoids using calculus that, hypothetically, is within the grasp of talented Precalculus students. Instead of treating this problem as a differential equation, we instead treat it as a first-order difference equation (also called a recurrence relation):

A_{n+1} = r A_n - k

The idea is that the amount owed is multiplied by a factor r (which is greater than 1), and from this product the amount paid is deducted. With this approach — and unlike the approach using calculus — the payment period would be each month and not per year. Therefore, we can write

A_{n+1} = \displaystyle \left( 1 + \frac{0.25}{12} \right) A_n - 50

Notice that the meaning of the 25% has changed somewhat… it’s no longer the relative rate of growth, as the 25% has been equally divided for the 12 months.

green lineA full treatment of the solution of difference equations belongs to a proper course in discrete mathematics. However, this particular difference equation can be solved in a straightforward fashion that should be accessible to talented Precalculus students. Let’s use the above recurrence relation to try to find a pattern. For n = 1, we find

A_1 = r A_0 - k = r P - k.

For n = 2, we find

A_2 = r A_1 - k

A_2 = r (rP - k) - k

A_2 = r^2P - rk - k

A_2 = r^2 P - k (1 + r)

For n = 3, we find

A_3 = r A_2 - k

A_3 = r \left[ r^2 P - k(1+r) \right] - k

A_3 = r^3 - rk(1+r) - k

A_3 = r^3 P - rk - r^2k - k

A_3 = r^2 P - k \left( 1 + r+r^2 \right)

At this point, we can probably guess a pattern:

A_n = r^n P - k \left( 1 + r + r^2 + \dots + r^{n-1} \right)

Using the formula for a finite geometric series, this simplifies as

A_n = r^n P - k \left( \displaystyle \frac{1 - r^n}{1-r} \right).

Indeed, though I won’t do it here, this can be formally proven using mathematical induction.

 

Zeno’s paradox

Source: http://www.xkcd.com/1153/

See also: https://meangreenmath.com/2013/09/16/formula-for-an-infinite-geometric-series-part-9/

An infinite number of mathematicians walk into a bar

An infinite number of mathematicians walk into a bar. The first one orders a beer, the second one orders a half a beer, the third orders a quarter of a beer, and this trend continues on for some time.

After a while, the bartender gets fed up and hands them 2 beers, shakes his head and says, “You mathematicians just don’t know your limits.”

Approximating pi

I was recently interviewed by my city’s local newspaper about \pi Day and the general fascination with memorizing the digits of \pi. I was asked by the reporter if the only constraint in our knowledge of the digits of \pi was the ability of computers to calculate the digits, and I answered in the affirmative.

Here’s the current state-of-the-art for calculating the digits of \pi. Amazingly, this expression was discovered  1995… in other words, very recently.

\pi = \displaystyle \sum_{n=0}^\infty \frac{1}{16^n} \left( \frac{4}{8n+1} - \frac{2}{8n+4} - \frac{1}{8n+5} - \frac{1}{8n+6} \right)

Because of the term 16^n in the denominator, this infinite series converges very quickly.

Proof: If k < 8, then we calculate the integral I_k, defined below:

I_k = \displaystyle \int_0^{1/\sqrt{2}} \frac{x^{k-1}}{1-x^8} dx

= \displaystyle \int_0^{1/\sqrt{2}} x^{k-1} \sum_{n=0}^\infty x^{8n} dx

= \displaystyle \int_0^{1/\sqrt{2}} \sum_{n=0}^\infty x^{8n+k-1} dx

= \displaystyle \sum_{n=0}^\infty \int_0^{1/\sqrt{2}} x^{8n+k-1} dx

= \displaystyle \sum_{n=0}^\infty \left[ \frac{x^{8n+k}}{8n+k} \right]^{1/\sqrt{2}}_0

= \displaystyle \sum_{n=0}^\infty \frac{1}{8n+k} \left[ \left( \frac{1}{\sqrt{2}} \right)^{8n+k} - 0 \right]

= \displaystyle \sum_{n=0}^\infty \frac{1}{2^{k/2}} \frac{1}{16^n (8n+k)}

We now form the linear combination P = 4\sqrt{2} I_1 - 8 I_4 - 4\sqrt{2} I_5 - 8 I_6:

P = \displaystyle \sum_{n=0}^\infty \left( \frac{4\sqrt{2}}{2^{1/2}} \frac{1}{16^n (8n+1)} - \frac{8}{2^{4/2}} \frac{1}{16^n (8n+4)} - \frac{4\sqrt{2}}{2^{5/2}} \frac{1}{16^n (8n+5)} - \frac{8}{2^{6/2}} \frac{1}{16^n (8n+6)} \right)

P = \displaystyle \sum_{n=0}^\infty \frac{1}{16^n} \left( \frac{4}{8n+1} - \frac{2}{8n+4} - \frac{1}{8n+5} - \frac{1}{8n+6} \right)

Also, from the original definition of the I_k,

P = \displaystyle \int_0^{1/\sqrt{2}} \frac{4\sqrt{2} - 8x^3 -4\sqrt{2} x^4 - 8x^5}{1-x^8} dx.

Employ the substitution x = y/\sqrt{2}:

P = \displaystyle \int_ 0^1 \frac{4\sqrt {2} - 2\sqrt {2} y^3 - \sqrt {2} y^4 - \sqrt {2} y^5}{1 - y^8/16}\frac {dy} {\sqrt {2}}

P = \displaystyle \int_ 0^1 \frac{16 (4 - 2 y^3 - y^4 - y^5)}{16 - y^8} dy

P = \displaystyle \int_0^1 \frac{16(y-1)(y^2+2)(y^2+2y+2)}{(y^2-2)(y^2+2)(y^2+2y+2)(y^2-2y+2)} dy

P = \displaystyle \int_0^1 \frac{16y-16}{(y^2-2)(y^2-2y+2)} dy

Using partial fractions, we find

P = \displaystyle \int_ 0^1\frac{4 y}{y^2 - 2} dy - \int_ 0^1 \frac{4 y - 8}{y^2 - 2 y + 2} dy

The expression on the right-hand side can be simplified using standard techniques from Calculus II and is equal to \pi.

green line

So that’s the proof… totally accessible to a student who has mastered concepts in Calculus II. But this begs the question: how in the world did anyone come up with the idea of starting with the integrals $I_k$ to develop an infinite series that leads to \pi? Let me quote from page 118 of J. Arndt and C. Haenel, \pi - Unleashed (Springer, New York, 2000):

Certainly not by chance, even if luck played some part in the discovery. All three parties [David Bailey, Peter Borwein and Simon Plouffe] are established mathematicians who have been working with the number \pi for a considerable time… Yet the series was not discovered through mathematical deduction or inference. Instead, the researchers used a tool called Computer Algebra System and a particular procedure called the “PSQL algorithm” to generate their series. They themselves write that they found their formula “through a combination of inspired testing and extensive searching.”

The original paper that announced the discovery of this series can be found at http://www.cecm.sfu.ca/personal/pborwein/PAPERS/P123.pdf.