Design and Analysis of Algorithms

Additional Exercises with Solutions 793

Multiply by the constant which appears as a coeffi cient of a

n–1

in the previous equation so the two terms

cancel out when we add both sides:

2a

n–1

= 2

2

an–2 + 2

Write down the equation for a

n–2

and multiply both sides by the coeffi cient of a

n–2

in the previous

equation:

a

n–2

= 2a

n–3

+ 1 becomes 2

2

a

n–2

= 2

3

a

n–3

+ 2

2

Continue till the initial condition appears on the right hand side:

a

1

= 2a

0

+ 1, becomes 2

n–1

a

1

= 2

n

a

0

+ 2

n–1

Add both sides of the equations and cancel identical terms:

1

0

0

22

n

ni

n

i

aa

−

=

=+

∑

Substitute a

0

and simplify

1

0

2

n

i

i

−

=

∑

to get the solution:

a

n

= 3(2

n

) + 2

n

– 1 = 2

n + 2

–1 ...