The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
143 views

Question:

$T(1)=1$

$T(n) = 2 T(n - 1) + n$

evaluates to?

Can anyone solve it by substitution method?


Given answer 

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

How? 

asked in Algorithms by (181 points)
edited by | 143 views
–1
O(2^n)
0
What I think is that if you try to somehow convert the expression you are getting into the given answer it's not easy and not obvious. The question seems like selection and elimination type. If you have four options then successively find out values, say upto T(5), and see which option's result is matching with your result.

There will be a way to adjust the expression by adding or subtracting some terms to get the answer but it will be cubersome.

2 Answers

0 votes

First see the procedure how to solve these type of questions below :-

Source :- Kenneth H. Rosen

Now, We can write the given Linear Non-Homogeneous Recurrence Relation as :-

$a_{n} - 2a_{n-1} = n$

Now, Characteristic Equation will be :-

$\alpha ^{n} - 2\alpha ^{n-1} = 0$

So, $\alpha = 2$

So, Solution of the associated homogeneous equation will be :- $a_{n}^{(h)} = c2^{n}$ where '$c$' is arbitrary constant.

Now, Let, Particular Solution is :- $a_{n}^{(p)} = P_0{n} + P_1$ where $P_0$ and $P_1$ are constant.

Now, $a_{n}^{(p)}$ will satisfy the given recurrence. So, It becomes,

$P_0*n + P_1 = 2(P_0(n-1)+P_1) + n$

After comparing coefficients , $P_0 =-1 $ and $P_1 =-2 $

So, $a_{n}^{(p)} = -{n} -2 $

Now, Solution of the given Recurrence is given by :-

$a_n = a_{n}^{(h)}+a_{n}^{(p)}$

$\Rightarrow$ $a_n = c2^{n}  -{n} -2$

Since, $a_1=1$ , So, $c=2$

So, $a_n = 2*2^{n}  -{n} -2$

$\Rightarrow$ $a_n = 2^{n+1}  -({n} +2)$

answered by Boss (13.7k points)
0 votes

TRICK

put any value in question and answer....if they match then correct solution

 

otherwise solve with substitution method... then you will get the answer

answered by (83 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,811 questions
54,530 answers
188,403 comments
75,483 users