@Abhinavg ,please correct me if anything is wrong..

1 vote

Use generating function to solve the recurrence relation $a_k=3{a_{k-1}} + 2$ with initial conditions $a_0=1 $.

0

Yes it is right but we have to do more to reach to a general form , and apply partial fraction after that , as done by pankaj_vlr.

0

life will be easy when we don't need to do by non-homogenous eq method or generating function. Maybe some time-saving solutions.

2 votes

$eq.1 \rightarrow$ $G(x) = \sum_{k = 0}^{\infty }a_{k}x^k$

multiply $G(x)$ with $3x$, we get

$eq.2 \rightarrow$ $3x.G(x) = \sum_{k = 0}^{\infty }3.a_{k}.x^{k+1}$

$eq.1 - eq.2$

$(1-3x).G(x) = \sum_{k = 0}^{\infty }a_{k}x^{k} - \sum_{k = 0}^{\infty }3.a_{k}.x^{k+1}$

$= a_{0} + \sum_{k = 1}^{\infty }a_{k}x^{k} - \sum_{k = 1}^{\infty }3a_{k-1}x^{k}$

$= a_{0} + \sum_{k = 1}^{\infty }(a_{k} - 3a_{k-1})x^{k}$

$= 1 + \sum_{k = 1}^{\infty }2x^{k}$ $\because a_{k} - 3a_{k-1} = 2$

$= 1 + 2\sum_{k = 1}^{\infty }x^{k}$

$= 1 + 2x/1-x$ $\because$ sum of infinite GP

$= (1 - x + 2x)/1-x$

$= (1 + x)/1-x$

$G(x)= (1 + x)/(1-x)(1-3x)$

By using partial fraction,

$(1 + x)/(1-x)(1-3x) = A/(1-x) + B/(1-3x)$

$(1 + x)/(1-x)(1-3x) = (A+B) + (-3A -B)/(1-x)(1-3x)$

on comparing $LHS$ and $RHS$, we get

$A+B = 1$

$-3A-B = 1$

on solving these equation, we get $A = -1$ and $B = 2$

$(1 + x)/(1-x)(1-3x) = -1/(1-x) + 2/(1-3x)$

$-1/(1-x) + 2/(1-3x) = -\sum_{k=0}^{\infty }x^k + 2\sum_{k=0}^{\infty } 3^kx^k$ $\because 1/(1-ax) = \sum_{k=0}^{\infty } a^kx^k$

$\sum_{k=0}^{\infty } (2.3^k - 1)x^k$

coefficient of $x^k$ is $2.3^k - 1$

$a_{k} = 2.3^k - 1$

multiply $G(x)$ with $3x$, we get

$eq.2 \rightarrow$ $3x.G(x) = \sum_{k = 0}^{\infty }3.a_{k}.x^{k+1}$

$eq.1 - eq.2$

$(1-3x).G(x) = \sum_{k = 0}^{\infty }a_{k}x^{k} - \sum_{k = 0}^{\infty }3.a_{k}.x^{k+1}$

$= a_{0} + \sum_{k = 1}^{\infty }a_{k}x^{k} - \sum_{k = 1}^{\infty }3a_{k-1}x^{k}$

$= a_{0} + \sum_{k = 1}^{\infty }(a_{k} - 3a_{k-1})x^{k}$

$= 1 + \sum_{k = 1}^{\infty }2x^{k}$ $\because a_{k} - 3a_{k-1} = 2$

$= 1 + 2\sum_{k = 1}^{\infty }x^{k}$

$= 1 + 2x/1-x$ $\because$ sum of infinite GP

$= (1 - x + 2x)/1-x$

$= (1 + x)/1-x$

$G(x)= (1 + x)/(1-x)(1-3x)$

By using partial fraction,

$(1 + x)/(1-x)(1-3x) = A/(1-x) + B/(1-3x)$

$(1 + x)/(1-x)(1-3x) = (A+B) + (-3A -B)/(1-x)(1-3x)$

on comparing $LHS$ and $RHS$, we get

$A+B = 1$

$-3A-B = 1$

on solving these equation, we get $A = -1$ and $B = 2$

$(1 + x)/(1-x)(1-3x) = -1/(1-x) + 2/(1-3x)$

$-1/(1-x) + 2/(1-3x) = -\sum_{k=0}^{\infty }x^k + 2\sum_{k=0}^{\infty } 3^kx^k$ $\because 1/(1-ax) = \sum_{k=0}^{\infty } a^kx^k$

$\sum_{k=0}^{\infty } (2.3^k - 1)x^k$

coefficient of $x^k$ is $2.3^k - 1$

$a_{k} = 2.3^k - 1$

0

$T\left ( n \right )=3T\left ( n-1 \right )+2$

$T\left ( n-1 \right )=3T\left ( n-2 \right )+2$

$T\left ( n-2 \right )=3T\left ( n-3 \right )+2$

...................................

replacing in T(n)

$T\left ( n \right )=3T\left ( n-1\right )+2$

$T\left ( n \right )=3\left [ 3T\left ( n-2\right )+2 \right ]+2$

$T\left ( n \right )=3^{2}T\left ( n-2 \right )+3.2+2$

$T\left ( n \right )=3^{3}T\left ( n-3 \right )+3^{2}.2+3.2+2$

--------------------------------------------------------------------------------

$T\left ( n \right )=3^{n}T\left ( 1 \right )+3^{n-1}.2+......3^{2}.2+3.2+2$

$T\left ( n \right )=3^{n}.1+3^{n-1}.2+......3^{2}.2+3.2+2$

$T\left ( n \right )=3^{n}+2\left [ 3^{n-1}+......3^{2}+3+1 \right ]$

$T\left ( n \right )=3^{n}+2\frac{3^{n-1}-1}{3-1}$

$T\left ( n \right )=3^{n}+3^{n-1}-1$

$T\left ( n-1 \right )=3T\left ( n-2 \right )+2$

$T\left ( n-2 \right )=3T\left ( n-3 \right )+2$

...................................

replacing in T(n)

$T\left ( n \right )=3T\left ( n-1\right )+2$

$T\left ( n \right )=3\left [ 3T\left ( n-2\right )+2 \right ]+2$

$T\left ( n \right )=3^{2}T\left ( n-2 \right )+3.2+2$

$T\left ( n \right )=3^{3}T\left ( n-3 \right )+3^{2}.2+3.2+2$

--------------------------------------------------------------------------------

$T\left ( n \right )=3^{n}T\left ( 1 \right )+3^{n-1}.2+......3^{2}.2+3.2+2$

$T\left ( n \right )=3^{n}.1+3^{n-1}.2+......3^{2}.2+3.2+2$

$T\left ( n \right )=3^{n}+2\left [ 3^{n-1}+......3^{2}+3+1 \right ]$

$T\left ( n \right )=3^{n}+2\frac{3^{n-1}-1}{3-1}$

$T\left ( n \right )=3^{n}+3^{n-1}-1$

0

its a_{k} - 3a_{k-1}_{ }= 2 ,rest is done right , maybe he missed there.

I was stuck at the partial fraction part .