The Gateway to Computer Science Excellence

+1 vote

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?

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.

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

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)$

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.4k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.7k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,666 questions

56,167 answers

193,838 comments

94,007 users