Question

where do I go from here? am I even on the right track?
Solve the following recurrence relation
P(1)=2
P(n)=2P(n-1)+n2^n for n>=2

P(2)=2P(2-1)+2*2^2
P(n)=2P(1)+8
P(n)=2*2+8
P(n)=4+8=12

base:
P(3)=2P(3-1)+3*2^3
P(3)=2P(2)+3*2^3
P(3)=2*12+24
P(3)=24+24=48

Answer 1

do i need to use some kind of telescoping algorithm?

Answer 2

this is new to me
let me try to telescoping algorithm thingy on this relation here...
\[P(n)=2P(n-1)+n2^{n} \\ P(n-1)=2P(n-2)+(n-1)2^{n-1} \\ P(n-2)=2P(n-3)+(n-2)2^{n-2} \\ P(n-3)=2P(n-4)+(n-3)2^{n-3} \\ \cdots \\ P(3)=2P(2)+3 \cdot 2^{3} \\ P(2)=2P(1)+2 \cdot 2^2 \\ \\ \text{ so adding up } \\ P(n)+P(n-1)+P(n-2)+ \cdots +P(3)+P(2) \\ =2P(n-1)+2P(n-2)+ \cdots +2 P(2)+2 P(1) \\ +n2^n+(n-1)2^{n-1}+(n-2)2^{n-2} \cdots +3 \cdot 2^3+2 \cdot 2^2\\ P(n)-P(n-1)-P(n-2)+\cdots -P(3)-P(2)-2P(1) \\ =n 2^{n}+(n-1)2^{n-1}+(n-2)^{n-2}+ \cdots + 3 \cdot 2^3+2 \cdot 2^2 \]
so I don't think the telescoping thing worked

hey the only way I can think of is just writing a few terms and seeing if I can guess the pattern; this way however doesn't always work because I can't always see the pattern

Answer 3

unless you have any other algorithms to mention

Answer 4

I dont know really, my class mate mention telescoping but im not sure really what to do with this other then "guess and check"

Answer 5

let me think some more

Answer 6

thank you!

Answer 7

\[P(n)-2P(n-1)=n2^{n} \\ P(n-1)-2P(n-2)=(n-1)2^{n-1} \implies 2P(n-1)-4P(n-2)=(n-1)2^n \\ \\ \text{ I multiplied both sides by 2 because when I add this equation \to the first } \\ \text{ the } P(n-1) \text{ term goes bye-bye }\]
I'm going to get doing this
next equation though I will multiply by 4
so maybe this is a telescoping problem

Answer 8

\[P(n-2)-2P(n-3)=(n-2)2^{n-2} \implies 4 P(n-2)-8P(n-3)=(n-2)2^{n}\]
see adding this to previous equation will get rid of P(n-2) term

Answer 9

we will keep doing this...
\[\text{ eventually giving us } \\ P(n)=n 2^{n}+(n-1) 2^{n}+(n-2) 2^{n} + \cdots +(3)2^{n}+(2)2^n+(1)2^n \\ P(n)=(n+(n-1)+(n-2)+\cdots +3+2+1) 2^n \\ \text{ and recall what } \frac{n(n+1)}{2} \text{ equals }\]

Answer 10

hmm thats cool

Answer 11

if this is a little more clear:
I'm just going to write everything I have:
\[P(n)-2P(n-1)=n2^n \\ \color{red}{2}[P(n-1)-2P(n-2)]=\color{red}{2}(n-1)2^{n-1} \\ \color{red}{2^2}[P(n-2)-2P(n-3)]=\color{red}{2^2}(n-2)2^{n-2} \\ \cdots \\ \color{red}{2^{n-3}}[P(3)-2P(2)]=\color{red}{2^{n-3}}(3)2^{3} \\ \color{red}{2^{n-2}}[P(2)-2P(1)]=\color{red}{2^{n-2}}(2)2^{2} \\ \text{ adding equations together } \\ P(n)-2^{n-2}(2)P(1)=(2+3+\cdots+ (n-2)+(n-1)+n)2^{n} \\ P(n)-2^{n-1}(2)=(2+3+ \cdots +(n-2)+(n-1)+n)2^{n} \\ P(n)-2^{n}=(2+3+ \cdots +(n-2)+(n-1)+n)2^{n} \\ P(n)=(1+2+3+ \cdots +(n-2)+(n-1)+n)2^{n} \\ \text{ and like I said to make this pretty recall } \\ \text{ what } \frac{n(n+1)}{2} \text{ equals }\]

Answer 12

and yes I did use law of exponents a lot above
for example:
\[2^{n-3}(3)2^3=2^{n-3+3}(3)=2^n(3)\]

Answer 13

P(n)=(((n(n+1))/2)(n−2)+(n−1)+n)2^n

Answer 14

you remember that 1+2+3+...+(n-2)+(n-1)+n is n(n+1)/2

Answer 15

(n(n+1))/2 is a way of incrementing by one correct?

Answer 16

like you mean
1=1(1+1)/2
1+2=2(2+1)/2
1+2+3=3(3+1)/2
...
1+2+3+...+n=n(n+1)/2
if so yes...

Answer 17

yes thats is what i mean i think, sorry im hitting brain burn out

Answer 18

so does it finally simplify to (n^3+n^2+2n-3)/2

Answer 19

are you using that 1+2+3+...+n is just n(n+1)/2?

Answer 20

\[P(n)-2P(n-1)=n2^n \\ \color{red}{2}[P(n-1)-2P(n-2)]=\color{red}{2}(n-1)2^{n-1} \\ \color{red}{2^2}[P(n-2)-2P(n-3)]=\color{red}{2^2}(n-2)2^{n-2} \\ \cdots \\ \color{red}{2^{n-3}}[P(3)-2P(2)]=\color{red}{2^{n-3}}(3)2^{3} \\ \color{red}{2^{n-2}}[P(2)-2P(1)]=\color{red}{2^{n-2}}(2)2^{2} \\ \text{ adding equations together } \\ P(n)-2^{n-2}(2)P(1)=(2+3+\cdots+ (n-2)+(n-1)+n)2^{n} \\ P(n)-2^{n-1}(2)=(2+3+ \cdots +(n-2)+(n-1)+n)2^{n} \\ P(n)-2^{n}=(2+3+ \cdots +(n-2)+(n-1)+n)2^{n} \\ P(n)=(1+2+3+ \cdots +(n-2)+(n-1)+n)2^{n} \\ \text{ and like I said to make this pretty recall } \\ \text{ what } \frac{n(n+1)}{2} \text{ equals }\]
...
\[P(n)=(1+2+ \cdots +n)2^{n} \\ P(n)=\frac{n(n+1)}{2}2^{n}\]

Answer 21

ohhhhh... yep that makes sense... wow sorry for being so brain dead