Question

Solve the recurrence relation using iteration:

$$a_n = a_{n-1} + 1 + 2^{n-1}\\
a_0 = 0$$

So $a_1$ = 2, $a_2$ = 5...

I really have no idea how to solve recurrence relations that aren't of the linear, homogeneous type with constant coefficients. How would I solve this one? by iteration? to *n*? It's undefined... What are the properties of this recurrence relation (linear, homogeneous, etc.) and why?

Then I'm supposed to be able to prove the solution to this by mathematical induction, I guess since it's solved "using iteration"... I don't know how to do this either.

Answer 1

Solve the recurrence relation using iteration:

\(a_n = a_{n-1} + 1 + 2^{n-1}\\
a_0 = 0\)

So \(a_1\) = 2, \(a_2\) = 5...

I really have no idea how to solve recurrence relations that aren't of the linear, homogeneous type with constant coefficients. How would I solve this one? by iteration? to *n*? It's undefined... What are the properties of this recurrence relation (linear, homogeneous, etc.) and why?

Then I'm supposed to be able to prove the solution to this by mathematical induction, I guess since it's solved "using iteration"... I don't know how to do this either.

Answer 2

i cheated and found the answer via wolfram
wondering what would happen if the \(2^{n-1}\) was not there i.e. if it was just
\[a_n=a_{n-1}+1\] would the answer be
\[a_n=c+n\]?

Answer 3

oh yes, clearly it would be that

Answer 4

now with the \(2^{n-1}\) there, i think you just kick the power up by one and get \[2^n\]

Answer 5

or maybe \[2^n-1\] since you are summing
\[\sum 2^{n-1}\]

Answer 6

try \[a_n=n+2^n\]

Answer 7

\[a_0=0\] so i guess that is wrong, try
\[a_n=n+2^n-1\]

Answer 8

Oh that looks good!! thank you!! but how are we supposed to get this, just by guessing? I was trying out similar formulas but hadn't quite gotten that one yet.