# Calculating accumulation

I would firstly like to point out that I am just becoming very interested in maths but have very little technical mathematical knowledge, so I, therefore, understand that the phenomenon that I'm talking about might not be called "accumulation", but I would be equally interested to hear what it's called.

There is a challenge where a person saves money. On day one they save one cent and every subsequent day they save the same amount as yesterday plus 1 cent. For example:

Day Number   Addition   Saving  Total Savings
(x)                             (y)
---------------------------------------------------

1            £0.01      £0.01   £0.01
2            £0.01      £0.02   £0.03
3            £0.01      £0.03   £0.06
4            £0.01      £0.04   £0.10
5            £0.01      £0.05   £0.15
6            £0.01      £0.06   £0.21
7            £0.01      £0.07   £0.28
8            £0.01      £0.08   £0.36
9            £0.01      £0.09   £0.45
10           £0.01      £0.10   £0.55


I am looking to create an equation to find the value of y (the total value of savings) for any given day number.

I know that essentially the calculation is:

(Day Number × 1 Cent) + (((Day Number)-1) × 1 cent))...


continued until day number is equal to 1

My question is: Is there a simple way to show to do this as an equation?

Let us denote the current savings by $$a_n$$ for the $$n^{th}$$ day, in pennies to make things simpler. Then we see that

$$a_n = a_{n-1} + n$$

because we start with $$a_{n-1}$$ in the savings, and add $$n$$ pennies (because on the given day we add one more penny than the previous and start at $$1$$ on day one). We have the initial condition that $$a_1=1$$ (we start with one penny saved on day one).

This defines a recurrence relation, where we can express future terms in a sequence by referring to the previous ones. This in particular is a "nonhomogenous" (we have some terms that do not reference previous terms), "linear" (each term refers to at most one previous term) recurrence relation.

This is a simple one and can be solved explicitly if you want a general form, one that does not rely on reference to previous terms (where you can just plug in $$n$$ and figure out what you have on day $$n$$). There are plenty of methods to solve this, but they might fly a little above your head. So I'll discuss the longer if more intuitive way to solve this.

Imagine iterating this recurrence relation backwards. The recurrence $$a_n = a_{n-1} + n$$ holds for any $$n \ge 1$$. So we also know that $$a_{n-1} = a_{n-2} + (n-1)$$ for $$n$$ large enough, for example. Let's use this fact and iterate back a few times...

\begin{align} a_n &= a_{n-1} + n\\ &= a_{n-2} + (n-1) + n\\ &= a_{n-3} + (n-2) + (n-1) + n\\ &= a_{n-4} + (n-3) + (n-2) + (n-1) + n\\ \end{align}

A pattern emerges! After $$k$$ back-iterations in this vein, we see

\begin{align} a_n &= a_{n-k} + (n-k+1) + (n-k+2) + (n-k+3) + \cdots + (n-1) + n \\ &= a_{n-k} + \sum_{i=1}^k (n-k+i) \end{align}

What happens if $$k=n-1$$? Then we can use our initial condition, as

$$a_n = a_{1} + \sum_{i=1}^{n-1} (n-(n-1)+i) = 1 + \sum_{i=1}^{n-1} (i+1)$$

What is that summation? If you write it out, we clearly see

$$\sum_{i=1}^{n-1} (i+1) = 2+3+4+\cdots+(n-3)+(n-2)+(n-1)+n$$

Why, this is almost like the sum of the first $$n$$ integers, aside from missing $$1$$, but our initial condition gives us that! Thus we can claim,

$$a_n = \text{(the sum of the first n integers)} = \sum_{i=1}^n i$$

(Arguably one could start at the above fact just by common sense - "I add one on day one, two on day two, three on day three, and so on, and I start with nothing.") Okay, but what is this sum? This is a common introductory proof by induction, but essentially we obtain

$$a_n = \frac{n(n+1)} 2$$

If you wish to see the details behind the proof, a search on MSE for "sum of the first $$n$$ integers" should bring up plenty of results.

Notably, one with good pattern recognition skills might recognize your "total savings" values, and realize the above is the solution right off, because $$1,3,6,10,15,\cdots$$ form a sequence of "triangular numbers," which are defined by this recurrence relation and have the general form highlighted above. Wikipedia has an article on them.

To then convert this into pounds, bear in mind that we have found the total number of pennies saved, so we can just divide by $$100$$. Accordingly, if $$y(n)$$ denotes the savings on day $$n$$, then

$$y(n) = \frac{a_n}{100} = \frac{n(n+1)}{200}$$