Solve the recurrence relation using iteration

[cilla]

Homework Statement

[/B]
Solve the recurrence relation (use iteration).

a_n = a_n-1 + 1 + 2^n-1
a₀ = 0

Then prove the solution by mathematical induction.

Homework Equations

The Attempt at a Solution

a₁ = 2
a₂ = 5
a₃ = 10
a₄ = 19
a₅ = 36

The solution appears to be a_n = n + 2ⁿ - 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.

 

[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?

 

[Ray Vickson]

Homework Statement

[/B]
Solve the recurrence relation (use iteration).

a_n = a_n-1 + 1 + 2^n-1
a₀ = 0

Then prove the solution by mathematical induction.

Homework Equations

The Attempt at a Solution

a₁ = 2
a₂ = 5
a₃ = 10
a₄ = 19
a₅ = 36

The solution appears to be a_n = n + 2ⁿ - 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.

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}$.

 

[cilla]

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?

Yeah that's what I did.

So how do I prove my solution by induction?

 

[cilla]

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}$.

What's that formula for though?

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

 

[Ray Vickson]

Yeah that's what I did.

So how do I prove my solution by induction?

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.

 

[vela]

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

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

So how do I prove my solution by induction?

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

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.

 

[cilla]

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.

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.