# Math Help - recurrence relations

1. ## recurrence relations

I am hoping that someone can check if I did the first relation correctly and then give me a clue as to how to attack the second one. Thank you for being willing to share your knowledge and time.

a sub n = 2 n a sub n-1 a sub zero = 1

a sub n = 2 n a sub n-1 + 2 n a sub n-2....2(n) (1)

a sub n = 2^n

The second problem is:

Solve a sub n = a sub n-1 + 1 + 2^n-1

I have no idea how to attack this and I am sorry I do not know how to enter subscripts!!!!

2. Originally Posted by frostking2
I am hoping that someone can check if I did the first relation correctly and then give me a clue as to how to attack the second one. Thank you for being willing to share your knowledge and time.

a sub n = 2 n a sub n-1 a sub zero = 1

a sub n = 2 n a sub n-1 + 2 n a sub n-2....2(n) (1)

a sub n = 2^n

The second problem is:

Solve a sub n = a sub n-1 + 1 + 2^n-1

I have no idea how to attack this and I am sorry I do not know how to enter subscripts!!!!
$A_0 = 1$
$A_n = 2n * A_{n-1}$

So do the first few:
$A_0 = (1)$
$A_1 = (1)*2(1)$
$A_2 = (1)*2(1)*2(2)$
$A_3 = (1)*2(1)*2(2)*2(3)$
$A_4 = (1)*2(1)*2(2)*2(3)*2(4)$

So we see that we can rewrite it like so:
$A_4 = (1)*2(1)*2(2)*2(3)*2(4) = (2*2*2*2)(4*3*2*1) = 2^44!$

So
$A_n = 2^nn!$

To prove it:
$A_1 = 2(1)A_0 = 2(1)(1) = 2$
$A_1 = 2^11!=2$
So our formula is true for n=1

$(1)*2(1)*2(2)*2(3)*...*2(n) = 2^nn!$

The next iteration will be 2(n+1) so multiply both sides by this:
$(1)*2(1)*2(2)*2(3)*...*2(n)*2(n+1) = 2^nn!2(n+1)$
$(1)*2(1)*2(2)*2(3)*...*2(n)*2(n+1) = (2*2^{n})[n!(n+1)]$
$(1)*2(1)*2(2)*2(3)*...*2(n)*2(n+1) = 2^{n+1}(n+1)! = A_{n+1}$

So by induction, it is true.

---------
Originally Posted by frostking2
Solve a sub n = a sub n-1 + 1 + 2^n-1
Does it give you an $A_0$ or $A_1$?

Also, can you use parenthases? I'm interpreting this as $A_n = A_{n-1}+1+2^{n-1}$ But I am not sure this is correct.

3. ## Clarification of problem

Originally Posted by angel.white
$A_0 = 1$
$A_n = 2n * A_{n-1}$

So do the first few:
$A_0 = (1)$
$A_1 = (1)*2(1)$
$A_2 = (1)*2(1)*2(2)$
$A_3 = (1)*2(1)*2(2)*2(3)$
$A_4 = (1)*2(1)*2(2)*2(3)*2(4)$

So we see that we can rewrite it like so:
$A_4 = (1)*2(1)*2(2)*2(3)*2(4) = (2*2*2*2)(4*3*2*1) = 2^44!$

So
$A_n = 2^nn!$

To prove it:
[tex]A_1 = 2(1)A_0 = 2(1)(1) = 2
$A_1 = 2^11!=2$
So our formula is true for n=1

$(1)*2(1)*2(2)*2(3)*...*2(n) = 2^nn!$

The next iteration will be 2(n+1) so multiply both sides by this:
$(1)*2(1)*2(2)*2(3)*...*2(n)*2(n+1) = 2^nn!2(n+1)$
$(1)*2(1)*2(2)*2(3)*...*2(n)*2(n+1) = (2*2^{n})[n!(n+1)]$
$(1)*2(1)*2(2)*2(3)*...*2(n)*2(n+1) = 2^{n+1}(n+1)! = A_{n+1}$

So by induction, it is true.

---------

Does it give you an $A_0$ or $A_1$?

Also, can you use parenthases? I'm interpreting this as $A_n = A_{n-1}+1+2^{n-1}$ But I am not sure this is correct.
You did by some miracle figure it out. a(0) = 0 in this problem sorry I forgot to write it down. The answer to your first one really helps me to understand the process for first order equations. Thanks so much for your patience

4. Originally Posted by frostking2
You did by some miracle figure it out. a(0) = 0 in this problem sorry I forgot to write it down. The answer to your first one really helps me to understand the process for first order equations. Thanks so much for your patience
$A_0 = 0$
$A_n = A_{n-1}+1+2^{n-1}$

So do the first few to see the pattern:
$A_0 = 0$
$A_1 = 0+1+2^0 = 1+1$
$A_2 = (1+2^0)+1+2^1 = (1+1) + (1+2)$
$A_3 = (1+2^0)+(1+2^1)+1+2^2 = (1+1) + (1+2) + (1+4)$
$A_4 = (1+2^0)+(1+2^1)+(1+2^2) + 1 + 2^3 = (1+1) + (1+2) + (1+4) + (1 + 8)$

Now evaluate it a bit:
$A_4= (1+2^0)+(1+2^1)+(1+2^2) + 1 + 2^3$
$= (1+1+1+1) + (2^0+2^1+2^2+2^3)$
$= (1+1+1+1) + (1+2+4+8)$
It should be readily apparent that 1+1+1+1 = 4 which is n, if you don't see that, then realize that it is $\sum_{i=1}^n 1 = n$

$=n+(2^0+2^1+2^2+2^3)$
Now, lets look at our sums of this for A_1 through A_4, and compare them to various powers of two since there is a very obvious correllation between the two (which is why I kept the 2^0 through 2^4 instead of just showing their values)
$A_1 = 1$ compare to $2^1=2$
$A_2 = 3$ compare to $2^2=4$
$A_3 = 7$ compare to $2^3=8$
$A_4 = 15$ compare to $2^4=16$

Notice that in each case, this portion of our value is one less than 2^n. So:
$n+(2^0+2^1+2^2+2^3) = n+2^n-1 = A_n$

----------

Now to prove it:
Inductive Hypothesis:
$A_n = (1+2^0) + ( 1+2^1) + (1+2^2) + ... + (1+2^{n-1}) = n+2^n-1$

Basis step:
Using $A_n = A_{n-1} + 1 + 2^{n-1}$
$A_1 = 0 1+2^{1-1} = 2$

Using $A_n = n+2^n-1$
$A_1 = 1+2^1 - 1 = 2$

Inductive Step:
$(1+2^0) + ( 1+2^1) + (1+2^2) + ... + (1+2^{n-1}) = n+2^n-1$

The next step in the sequence is to add $(1+2^{n-1+1}) = (1+2^n)$ to both sides.
$(1+2^0) + ( 1+2^1) + (1+2^2) + ... + (1+2^{n-1}) + (1+2^n)= n+2^n-1+(1+2^n)$

$= (n+1)+(2^n+2^n)-1$
$= (n+1)+2^n(1+1)-1$
$= (n+1)+2^n*2-1$
$= (n+1)+2^{n+1}-1 = A_{n+1}$

So by induction, it is true taht $A_n = n+2^n-1$