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!!!!
$\displaystyle A_0 = 1$
$\displaystyle A_n = 2n * A_{n-1}$

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

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

So
$\displaystyle A_n = 2^nn!$

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

$\displaystyle (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:
$\displaystyle (1)*2(1)*2(2)*2(3)*...*2(n)*2(n+1) = 2^nn!2(n+1)$
$\displaystyle (1)*2(1)*2(2)*2(3)*...*2(n)*2(n+1) = (2*2^{n})[n!(n+1)]$
$\displaystyle (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 $\displaystyle A_0$ or $\displaystyle A_1$?

Also, can you use parenthases? I'm interpreting this as $\displaystyle 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
$\displaystyle A_0 = 1$
$\displaystyle A_n = 2n * A_{n-1}$

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

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

So
$\displaystyle A_n = 2^nn!$

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

$\displaystyle (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:
$\displaystyle (1)*2(1)*2(2)*2(3)*...*2(n)*2(n+1) = 2^nn!2(n+1)$
$\displaystyle (1)*2(1)*2(2)*2(3)*...*2(n)*2(n+1) = (2*2^{n})[n!(n+1)]$
$\displaystyle (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 $\displaystyle A_0$ or $\displaystyle A_1$?

Also, can you use parenthases? I'm interpreting this as $\displaystyle 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
$\displaystyle A_0 = 0$
$\displaystyle A_n = A_{n-1}+1+2^{n-1}$

So do the first few to see the pattern:
$\displaystyle A_0 = 0$
$\displaystyle A_1 = 0+1+2^0 = 1+1$
$\displaystyle A_2 = (1+2^0)+1+2^1 = (1+1) + (1+2)$
$\displaystyle A_3 = (1+2^0)+(1+2^1)+1+2^2 = (1+1) + (1+2) + (1+4)$
$\displaystyle 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:
$\displaystyle A_4= (1+2^0)+(1+2^1)+(1+2^2) + 1 + 2^3$
$\displaystyle = (1+1+1+1) + (2^0+2^1+2^2+2^3)$
$\displaystyle = (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 $\displaystyle \sum_{i=1}^n 1 = n$

$\displaystyle =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)
$\displaystyle A_1 = 1$ compare to $\displaystyle 2^1=2$
$\displaystyle A_2 = 3$ compare to $\displaystyle 2^2=4$
$\displaystyle A_3 = 7$ compare to $\displaystyle 2^3=8$
$\displaystyle A_4 = 15$ compare to $\displaystyle 2^4=16$

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

----------

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

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

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

Inductive Step:
$\displaystyle (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 $\displaystyle (1+2^{n-1+1}) = (1+2^n)$ to both sides.
$\displaystyle (1+2^0) + ( 1+2^1) + (1+2^2) + ... + (1+2^{n-1}) + (1+2^n)= n+2^n-1+(1+2^n)$

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

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