# Solve the recurrence relation using iteration

Tags:
1. Dec 5, 2014

### cilla

1. The problem statement, all variables and given/known data

Solve the recurrence relation (use iteration).

an = an-1 + 1 + 2n-1
a0 = 0

Then prove the solution by mathematical induction.

2. Relevant equations

3. The attempt at a solution

a1 = 2
a2 = 5
a3 = 10
a4 = 19
a5 = 36

The solution appears to be an = n + 2n - 1

How are we supposed to get that though? I just guessed and did trial and error. That's really the only/primary way?

Also, what are the properties of this recurrence relation (e.g., linear, homogeneous, etc.)? Why?

Also sorry if this is posted in the wrong section, I didn't know where it belongs if not here.

So how do I prove (or disprove, since I've only tried it out for so many of these) my solution using induction?

Thank you so much.

Last edited: Dec 5, 2014
2. Dec 5, 2014

### pasmith

$a_1 = a_0 + 1 + 2^0 = 1 + (2 - 1)$
$a_2 = a_1 + 1 + 2^1 = 1 + 2^0 + 1 + 2^1 = 2 + (1 + 2) = 2 + (4 - 1)$
$a_3 = a_2 + 1 + 2^2 = 2 + (1 + 2) + 1 + 2^2 = 3 + (1 + 2 + 4) = 3 + (8 - 1)$
etc...

Can you spot any patterns?

3. Dec 5, 2014

### Ray Vickson

Use the fact that $a_n - a_1 = (a_n - a_{n-1}) + (a_{n-1} - a_{n-2}) + \cdots + (a_2 - a_1)$, and you have a formula for $a_k - a_{k-1}$.

4. Dec 6, 2014

### cilla

Yeah that's what I did.

So how do I prove my solution by induction?

5. Dec 6, 2014

### cilla

What's that formula for though?

For proof by induction I need to make $a_{k+1} = (k+1) + 2^{k+1} -1$ right?

6. Dec 6, 2014

### Ray Vickson

Are you claiming that you have never seen the formula for $\sum_{k=1}^n r^k$? You can look in books or on-line for an answer.

HInt: geometric series.

Last edited: Dec 6, 2014
7. Dec 6, 2014

### vela

Staff Emeritus
What does linear mean? What does homogeneous mean? These are basic definitions you should look up for yourself.

There's a bit more to it. There are two parts to a proof by induction. Do you know what they are? If not, you should find out what they are. Apparently, this is something you're already supposed to know.

8. Dec 6, 2014

### cilla

Yeah. I know. You do the base step, then the induction step. I didn't have the starting form right, was confused about what I was supposed to actually be proving... I was just thinking to prove the k+1 part but what I'm supposed to be proving is that the initial recurrence relation formula given is equal to the one I got. Once I realized that (I know, seems painfully obvious), I got it. Thanks.