Question

Prove recurrence relation solution by induction:

Initial recurrence relation:
\(a_n = a_{n-1} + 1 + 2^{n-1}; a_0 = 0\)

Solution:
\(a_n = n + 2^n - 1\)

Answer 1

oh it was right?

Answer 2

Seemingly so! We won't know until we prove it though ;)

Answer 3

assume \[a_k=k+2^k-1\] prove
\[a_{k+1}=(k+1)+2^{k+1}-1\] aka
\[a_{k+1}=k+2^{k+1}\]

Answer 4

Good start...

Answer 5

it is mostly algebra since
\[a_{k+1}=a_k+1+2^{k-1}\] and you can replace \(a_k\) by \(k+2^k-1\) by induction

Answer 6

you get it right away

Answer 7

i don't get it :(

Answer 8

do you get that by induction
\[a_{k+1}=k+2^k-1+1+2^{k-1}\]

Answer 9

no i don't know induction

Answer 10

\[a_{k+1}=\overbrace{k+2^k-1}^{a_k}+1+2^{k-1}\]

Answer 11

we replace \(a_k\) by the formula we assume to be true

Answer 12

ok then what

Answer 13

algebra to show that \[a_{k+1}=(k+1)+2^{k+1}-1\] which is the formula with \(n\) replaced by \(k+1\)

Answer 14

it is not so easy to explain the idea behind induction here in a chat box, i am tempted to say that if you do not know how to do a proof by induction then you cannot do it
but what i wrote is what you have to do, and it comes down to algebra in showing that \[a_{k+1}=\overbrace{k+2^k-1}^{a_k}+1+2^{k-1}=(k+1)+2^{k+1}-1\]

Answer 15

ok then where or how can it be explained to me? you know of any reliable resources on the web that might drive the point home?

Answer 16

it is probably in your text, or you can google it
first you show it is true for \(n=1\)
then you assume it is true for \(n=k\) and using that assumption prove it is true for \(n=k+1\)
there are piles of youtube vidoes usually dealing with summation formulas

Answer 17

alright i'll try to figure it out thank you

Answer 18

yw