Mumbai University > Computer Engineering > Sem 3 > Discrete Structures

Marks: 6 Marks

Year: May 2016

Step1:

Let n = 0. Then, the left hand side will be

LHS = 1... 1 = 1, and

RHS = $\dfrac{1-a^{n+1}}{1-a} = [1 - a] / [1 - a] = 1$

so the formula holds true for n = 0

Step2:

Assume the formula holds true for n = k. That is,

$1+ a + a^2+....a^k= \dfrac{1-a^{k+1}}{1-a}$

Then the sum of the first (k + 1) terms would be the same as the sum of the first k terms, plus the (k + 1)th term. That is

$1+ a + a^2+....a^{k+1}= \{1+ a + a^2+....a^k\} +a^{k+1}$

But, look at the terms I placed in the { } brackets; by our induction hypothesis, this is equal to $\dfrac{1-a^{k+1}}{1-a}$.

Therefore

$1+ a + a^2+....a^{k+1}= [\dfrac{1-a^{k+1}}{1-a}] + a^{k+1}$

Putting them under a common denominator,

$1+ a + a^2+....a^{k+1}= \\ [\dfrac{1-a^{k+1}}{1-a}]+ (1 - a) a^{k+1} / (1 - a)$

Putting them under a single denominator,

$1+ a + a^2+....a^{k+1}= \\ [1 - a^{k+1} + (1 - r) a^{k+1}] / (1 - a)$

Distributing the $r^{k + 1}$ over the (1 - r), we have

$1+ a + a^2+....a^{k+1}= \\ [1 - a^{k+1}+ (a^{k+1}- a*a^{k+1}] / (1 - a)$

Simplifying some more, note that $a*a^{k+1}$ would be $a^{k+2}$

$1+ a + a^2+....a^{k+1}= \\ [1 - a^{k+1}+ a^{k+1}- a^{k+2}] / (1 - r)$ But, we have two terms that cancel each other out.

$1+ a + a^2+....a^{k+1}= [1 - a^{k+2} / (1 - a)$

OR,

$1+ a + a^2+....a^{k+1}= [1 - a^{k+1} + 1 ) / (1 - a)$

Which proves that the formula holds true for n = k + 1.

Therefore, by the principal of mathematical induction, the formula holds true for all n > = 0.