0

Could anyone show how to solve the recurrence $T(n) = 2T(n-1)+n-1$ with the initial condition $T(1) = 0$ by iteration? I've written out a couple levels of the recurrence in an attempt to see some sort of useful pattern, but I'm lost on this one. Here is what I have so far:

$\begin{array} \ T(1) &= 0 \\ T(2) &=2T(1)+n-1 &=2 \ (0) &+2-1&=2^1-1 \\ T(3) &=2T(2)+n-1 &=2\left(2^1-1\right) &+3-1&=2^2+0 \\ T(4) &=2T(3)+n-1 &=2\left( 2^2+0\right) &+4-1&=2^3+3 \\ T(5) &=2T(4)+n-1 &=2\left( 2^3+3 \right) &+5-1&=2^4 +10\\ T(6) &=2T(5)+n-1 &=2\left( 2^4+10\right) &+6-1&=2^5 +25\\ T(7) &=2T(6)+n-1 &=2\left(2^5+25 \right) &+7-1&=2^6+56 \\ \end{array}$

For the love of maths
  • 2,368
an0n1234
  • 5
  • 1
  • First you must find a solution to the homogenous equation $T_n-2T_{n-1}=0$, and then find a particular solution, for which I suggest you to try a polynomial of degree 1. – Fede Poncio Jan 28 '19 at 04:00
  • See https://math.stackexchange.com/questions/3080437/how-to-solve-vn-2-cdot-vn-1-2-cdot-n/3080533#3080533 – lab bhattacharjee Jan 28 '19 at 04:04
  • @Fede Poncio I've tried using $An - B$ as a guess for the particular solution, since $f(n) = n - 1$, but this led me to an irreducible equation with 3 unknowns. Is $An - B$ the correct form for a particular solution in this instance? – an0n1234 Jan 29 '19 at 01:37

1 Answers1

1

Hint Multiply each row by an extra power of 2.

$$\begin{array}{ccc} T(n) &= 2T(n - 1) &+ n - 1 \\ 2T(n-1) &= 4T(n - 2) &+ 2(n - 2) \\ 4T(n-2) &= 8T(n - 3) &+ 4(n - 3) \\ ...&...&...\\ 2^{n-1}T(1)&=2^nT(0)&+2^{n-1} \cdot 0 \end{array}$$

Now add everything together.

N. S.
  • 132,525
  • I apologize, could you provide more details on how this simplifies the problem? Thanks for your help. – an0n1234 Jan 29 '19 at 02:09
  • @an0n1234 What is the coefficient of $T(n-1)$ on LHS and RHS? What about $T(n-2)$? $T(n-3)$? Did you add everything up? – N. S. Jan 29 '19 at 02:29
  • The coefficient of $T(n - 1)$ is 2 for LHS and RHS. For $T(n - 2)$ and $T(n - 3)$ the coefficients are 4 and 8 respectively, both for LHS and RHS. Adding everything up, I have $T(n) + 2T(n-1) + 4T(n-2) + ... + 2^{n-1}T(1) = 2T(n-1) + n - 1 + 4T(n-2) + 2(n - 2) + 8T(n-3) + 4(n - 3) + ... + 2^nT(0)$ – an0n1234 Jan 29 '19 at 03:18
  • @an0n1234 Now you can cancel $2T(n-1), 4T(n-2), 8T(n-3),..$ – N. S. Jan 29 '19 at 04:11