1

How would I convert the below geometric (I assume based on the terms) recursive sequence summation to a closed formula?

$$a_1 = 1,\ \quad a_k = \sum_{i=1}^{k-1} a_i \ \quad for\ k \geqq 2$$

I've tried:

$$a_k = 2\frac{k-1}{k}$$

$$a_k = 2\frac{1-k^2}{1-k}$$

$$a_k = k\frac{1-k^2}{1-k}$$

But nothing seems to work correctly with the terms (with $a_1$ to $a_7$ being 1, 1, 2, 4, 8, 16, and 32 respectively). I'm pretty stuck and really not sure how to proceed so would appreciate any help.

UPDATE: Thanks for the help everyone, in truth it was a combination of the answers that helped me better understand how to proceed with this so for future users looking to understand this question better, I would advise going through all the answers and not just the chosen one.

Jess
  • 13
  • 5
  • 1
    Hint: what is $a_k-a_{k-1},$? – dxiv Sep 26 '21 at 06:47
  • Well for this sequence I guess that would give me the previous term with the exception of a1 and a2 which are both 1, but I'm not sure how to implement that into a formula for the summation... – Jess Sep 26 '21 at 07:09
  • So you get $a_k-a_{k-1}=a_{k-1}$ for $k \gt 2$, which is the same as $a_k = 2 a_{k-1}$, which is a geometric progression. – dxiv Sep 26 '21 at 07:14
  • Ok I see, but this needs to apply to k ≧ 2 and for $a_2$ (which is 1) it doesn't hold up, I get 2... – Jess Sep 26 '21 at 07:26
  • The GP starts at $k=2$, so you'll get a piecewise formula $a_1=1$ and $a_k=$ for $k \ge 2$. – dxiv Sep 26 '21 at 07:31
  • Hmm, sorry I'm a bit new with this subject so I'm probably missing something that may seem obvious to you but I'm still not sure. To have a working formula that represents the summation above, don't I need it to work for all the $a_k$ terms where k≥2. And to check that formula is correct I should be able to plugin any of the terms and get the correct value, is that not correct? In this case including $a_2$. – Jess Sep 26 '21 at 07:39
  • You don't get a monolithic formula, but a piecewise one $ \begin{align} a_n = \begin{cases} 1 &n=1 \ 2^{n-2} &n \ge 2 \end{cases} \end{align} ,$. – dxiv Sep 26 '21 at 07:45
  • Thanks dxiv, I've moved this over to Cesareo's answer for convenience. – Jess Sep 26 '21 at 09:24
  • Once you derived the recurrence relation $a_2=1, a_k=2a_{k-1} \mid k \ge 3$ there is no longer any summation in the picture. At that point you either know the GP formula and use it directly, or you can prove the GP formula - but you do that based on the recurrence, not the original summation form. – dxiv Sep 26 '21 at 16:31

3 Answers3

1

If you look at the sequence you have written out:

n an
1 1
2 1
3 2
4 4
5 8
6 16
7 32

Looking at this table we guess that $a_k = 2^{k-2}$ for $k >= 2$

We want to prove this by induction. the base case is simple $n=2$, as we have seen it holds above in the calculation.

For the inductive step, assume it is true for all $i$ up to $a_n$, that is, assume $i \leq n \implies a_i = 2^{i-1}$. We want to show that it then must hold for $a_{n+1}$, or explicitly that $a_{n+1} = 2^{n-1}$

From the recursive relation, $a_{n+1} = \sum_{i=1}^{n} a_i$. Using our inductive assumption, we can rewrite this $\sum_{i=1}^{n} a_i = \sum_{i=1}^{n} 2^{n-2}$.

As a partial sum of geometric series, $\sum_{i=1}^{n} 2^{n-2} = 2^{n-1}$. But this shows that $a_{n+1} = 2^{n-1}$ and the inductive hypothesis is proven.

user157545
  • 326
  • 2
  • 7
  • Well my guess at an explicit formula for the above relation would be 2^n-2, but I would need the recursive formula for the summation to verify. – Jess Sep 26 '21 at 07:07
  • So if you guess at the formula, you can prove it by induction. Check it for a1, and show if it holds for an then it holds for an+1 – user157545 Sep 26 '21 at 07:33
  • Yes thank you, I do see what you mean, but I think it's the summation that's throwing me off. If it were any other formula I believe I could work it out but here my first step was to convert that summation into a more workable formula and then plug in my explicit formula into the recursive formula and then simplify till they match, but I got stuck at the conversion of the summation stage... – Jess Sep 26 '21 at 07:46
  • Just to follow up here - I'm still not quite clear on what the summation formula converts to, as I'm not sure how to plugin $2^{k-2}$ into the current recursive summation during my inductive step, as my goal is to prove that my explicit formula satisfies the recursive one. So for example I'm trying to convert the summation in a similar manner to the example below...$$\sum_{i=0}^{n-1}a^i = \frac{1-a^n}{1-a}$$ So please any further help with that would be great. – Jess Sep 26 '21 at 09:41
  • Have updated the answer with more detail on our how to prove it. By taking a stronger inductive hypothesis (that it holds for all i less than n, rather than just for n, you can substitute the new result in for the entire summation. – user157545 Sep 26 '21 at 12:11
  • If I understand your question, you are trying to take a step in the proof where you say something along the lines of $\sum a_i = X$ for some closed form X. The approach used here, is instead to use strong induction, where you assume the relation holds for $i \leq n$. By doing this, you can substitute in for every term in the sum $\sum a_i = \sum 2^{i-2}$ and work with the entire summation. – user157545 Sep 26 '21 at 12:19
0

We claim that $$a_k=2^{k-2}$$ for $n\geq 2$.

To prove that, we will use Strong Induction.

$$a_k = \sum_{i=1}^{k-1} a_i=1+\sum_{i=2}^{k-1}2^{i-2}$$

To calculate the sum, let's use $m=i-2$ and see that the sum becomes $$1+\sum_{m=0}^{k-3}2^m=1+1\times \frac{2^{k-2}-1}{2-1}=1+2^{k-2}-1=2^{k-2}$$

This completes the proof.

Sayan Dutta
  • 8,831
  • Thank you Sayan, I think I am having trouble with the inductive step, mainly trying to plug in the explicit formula ($2^{k-2}$) into the recursive formula but as the recursive formula is a summation, I do not know how to do this. So I was attempting to convert the summation into a formula I am more comfortable with, similar to this example...$$\sum_{i=0}^{n-1}a^i = \frac{1-a^n}{1-a}$$ ...but I do not know how to do a like conversion with the summation from my question, if you could please help with this step I would be grateful. – Jess Sep 26 '21 at 10:20
  • @Jess to be honest, I didn't completely understand what you said. But, check my edit and see if that's okay with you. If not, feel free to ask again. – Sayan Dutta Sep 26 '21 at 10:51
0

We have $a_k = S_{k-1}$ then $a_k - a_{k-1} = S_{k-1}-S_{k-2} = a_{k-1}$ then for $k \ge 2$ we have the equivalent recurrence

$$ a_k = 2 a_{k-1}\Rightarrow a_k = c_0 2^k $$

Cesareo
  • 33,252
  • Sorry but I am a bit of a novice with this subject but what does "$c_0$" represent? And for $2a_k-1$, this wouldn't stand up for $a_2$ which is 1, no? – Jess Sep 26 '21 at 07:31
  • $c_0$ is a generic constant which can be determined using the initial conditions. In our case, as $a_1 = c_02^1 = 1$ makes $c_0 = \frac 12$ so finally, $a_k = 2^{k-1}$. – Cesareo Sep 26 '21 at 07:40
  • @Cesareo OP's sequence appears to be starting with $,a_1=a_2=1,$. – dxiv Sep 26 '21 at 07:46
  • Then $a_2=c_0 2^2 = 1$ which makes $c_0 = 2^{-2}$ and $a_k = 2^{k-2}$. Thanks. – Cesareo Sep 26 '21 at 07:55
  • Ok I see where your going with that, you're both giving me the explicit formula for the sequence which yes I did figure out. But what I want to do is now prove the explicit formula satisfies the recursive formula. And so I would go about doing this with induction of course but I don't know how to plug in $2^{k-2}$ into the summation indicated above without first converting the summation into I guess a closed equation, of which it would be easier to plug in my explicit formula, if that makes sense? For example...$$\sum_{i=0}^{n-1}a^i = \frac{1-a^n}{1-a}$$ – Jess Sep 26 '21 at 09:20
  • ...and so its the conversion of the summation into a like formula as the example that I am unsure of how to do. – Jess Sep 26 '21 at 09:22