Answer to Question #98921 in Discrete Mathematics for Dristanta Wagle

Question

Xn
i=1
i2
i = (n − 1)2n+1 + 2

Answer 1

Using induction to prove

We need prove a statement $\sum_{i=0} ^ {n} i \times 2^i = (n - 1) \times 2^{n+1} + 2$

Proof:

for n = 1

LHS =

$$\sum_{i=0} ^ {1} i \times 2^i = 2$$

RHS =

$$(n - 1) \times 2^{n+1} + 2 = 0 + 2 = 2$$

$$LHS = RHS$$

The given statement is true for n= 1

Let the given statement is true for n = k (integer)

$$\sum_{i=0} ^ {k} i \times 2^i = (k - 1) \times 2^{k+1} + 2$$

Now, Let n = k +1

$$\sum_{i=0} ^ {k+1} i \times 2^i = \sum_{i=0} ^ {k} i \times 2^i + ( k+1 ) \times 2^{k+1}$$

$$= (k - 1) \times 2^{k+1} + 2 + (k+1 ) \times 2^ {k+1}$$

$= k \times 2^ {k+1} - 2^ {k+1} + 2 + k \times 2^{k+1} + 2^{k+1}$

$$= 2k \times 2^ {k+1} + 2 = k \times 2 ^ {k+1+1} + 2$$

$$\sum_{i=0} ^ {k+1} i \times 2^i = (k+1 -1) \times 2^ {k+1+1} + 2$$

The given statement is true for n = k+1. By the principle of mathematical induction, it was proved that

$\sum_{i=0} ^ {n} i \times 2^i = (n - 1) \times 2^{n+1} + 2$