A Bit Of Help Please. Induction Arguments

AJL · November 10th 2006, 07:17 PM

If I could get some help on this as soon as possible, that would be great.

Here are the quesitons (I took a screenshot because I'm lazy like that

)

**Soroban** · November 10th 2006, 07:57 PM

Hello, AJL!

Here's the first one . . .

$1)\;1 + 5 + 9 + \hdots + (4n+1) \:=\:(n+1)(2n+1)$

Verify $S(1):\;1 + 5 \:=\:(1+1)(2\cdot1+1)$ . . . true!

Assume $S(k)\!:\;1 + 5 + 9 + \hdots + (4k+1) \:=\:(k+1)(2k+1)$

Add $4(k+1) + 1$ to both sides:

. . $1 + 5 + 9 + \hdots + (4k+1) +[4(k+1)+1]\:=\:(k+1)(2k+1) + [4(k+1)+1]$

The right side is: . $2k^2 + 3k + 1 + 4k + 4 + 1 \:=\:2k^2+7k+6 \:=\:(k+2)(2k+3)$

Hence, we have: . $1 + 5 + 9 + \hdots + (4k+1) +[4(k+1)+1]\:=\:[(k+1)+1][2(k+1) + 1]$

And we have proved $S(k+1)$ . . . Therefore, $S(n)$ is true.

**topsquark** · November 11th 2006, 04:24 AM

2) $2^{2n}-1$ is divisible by 3 for n = 1, 2, 3,...

The n = 1 case is trivial: $2^{2 \cdot 1} - 1 = 3$ .

So assume the problem is true for n = k. Then we need to show that
$2^{2(k+1)} - 1$ is divisible by 3.

Let $2^{2k} - 1 = 3m$ for some integer m. Then we know that $2^{2k} = 3m + 1$ .

Now, $2^{2(k+1)} = 2^{2k+2} = 4 \cdot 2^{2k} = 4(3m + 1) = 12m + 4$

So $2^{2(k+1)} - 1 = 12m + 4 - 1 = 12m + 3 = 3(4m + 1)$ .

Thus $2^{2(k+1)} - 1$ is divisible by 3.

If you know modular Mathematics:

$2^{2k}-1 \equiv 0$ (mod 3) then $2^{2k} \equiv 1$ (mod 3). Thus $2^{2(k+1)} = 2^{2k+2} = 4 \cdot 2^{2k}\equiv 1 \cdot 1 = 1$ (mod 3). Thus $2^{2(k+1)} - 1 \equiv 0$ (mod 3).

Thus $2^{2(k+1)} - 1$ is also divisible by 3.

-Dan

**topsquark** · November 11th 2006, 04:37 AM

3) $\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + ... + \frac{1}{n \cdot (n+1)} = \frac{n}{n+1}$

For n = 1:
$\frac{1}{1 \cdot 2} = \frac{1}{1+1} = \frac{1}{2}$
Check!

Assume this is true for some n = k. We need to show that
$\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + ... + \frac{1}{(k+1)(k+2)} = \frac{k+1}{k+2}$

Well, the first k terms of this sum to $\frac{k}{k+1}$ according to assumption, so we need to show
$\frac{k}{k+1} + \frac{1}{(k+1)(k+2)} = \frac{k+1}{k+2}$

$\frac{k}{k+1} + \frac{1}{(k+1)(k+2)}$

$\frac{k(k+2)}{(k+1)(k+2)} + \frac{1}{(k+1)(k+2)}$

$\frac{k(k+2)+1}{(k+1)(k+2)}$

$\frac{k^2+2k + 1}{(k+1)(k+2)}$

$\frac{(k+1)^2}{(k+1)(k+2)}$

$\frac{k+1}{k+2}$

As advertised.

-Dan

**topsquark** · November 11th 2006, 04:40 AM

HINT: Use the same technique on 4 that I used in 3.

HINT: The same comment applies for 5, but you need to add a lot of fractions to get there!

-Dan

**topsquark** · November 11th 2006, 04:49 AM

6) $2n+1 < 2^n$

For n = 3:
$2 \cdot 3 + 1 = 7 < 8 = 2^3$
Check!

Assume this is true for some n = k. We need to show that:
$2(k+1) + 1 < 2^{k+1}$

$2k + 3 \, ? \, 2 \cdot 2^k$ <-- Divide both sides by 2

$k + \frac{3}{2} \, ? \, 2^k$

But we know that $k + \frac{3}{2} < 2k + 1$ (You can verify this yourself.)

Thus $k + \frac{3}{2} < 2k + 1 < 2^k$

Thus $2k + 3 < 2^{k+1}$ (After multiplying both sides by 2, just to make things clearer.)

-Dan

**topsquark** · November 11th 2006, 04:59 AM

7) T(0) = 1 and T(n) = 2nT(n-1). Show that $T(n) = 2^nn!$ .

First, to get rid of the n = 0 case:
$T(0) = 2^00! = 1 \cdot 1 = 1$
Check!

Now,
$T(1) = 2 \cdot 1 \cdot T(0) = 2$
and
$2^11! = 2 \cdot 1 = 2$
Check!

So assume this is true for n = k.

We need to show that $T(k+1) = 2(k+1) T(k) = 2^{k+1}(k+1)!$

If the theorem is true for n = k, then $T(k) = 2^kk!$ . So we need to show that
$2(k+1) \cdot 2^kk! = 2^{k+1}(k+1)!$

Well, rearranging the LHS a bit:
$2(k+1) \cdot 2^kk! = \left ( 2\cdot 2^k \right ) (k+1)k! = 2^{k+1}(k+1)!$
as advertised.

-Dan

**Soroban** · November 11th 2006, 05:18 AM

Hello again, AJL!

$\text{If }\,T(0) = 1\,\text{ and }\,T(n) \,= \,2n\!\cdot\!T(n-1)\, \text{ for }n \geq 1$ ,

$\text{then: }\:T(n) \:=\:2^n\!\cdot\!n!\,\text{ for all }n \geq 0.$

Verify $S(1):\;\begin{array}{cc}T(1)\:= \\ T(1)\:=\end{array}<br /> \begin{array}{cc}2\!\cdot\!1\!\cdot\!1 \\ 2^1\!\cdot\!1!\end{array}<br /> \begin{array}{cc}=\:2 \\ =\:2\end{array}$ . . . True!

Assume $S(k):\;T(k) \:=\:2^k\!\cdot\!k!$

Multiply both sides by $2(k+1)\!:$

. . $2(k+1)\!\cdot\!T(k) \;= \;\underbrace{2^k\!\cdot\!2}_\downarrow\cdot\!\und erbrace{(k+1)\!\cdot\!k!}_\downarrow$
. . $\underbrace{2(k+1)\!\cdot\!T(k)}_{\text{This is S(k+1)}} \;=\;2^{k+1}\cdot(k+1)!$

Hence: . $T(k+1) \:=\:2^{k+1}\!\cdot(k+1)!$

Therefore, $S(n)$ is true for all $n \geq 0.$

**earboth** · November 11th 2006, 09:51 AM

Originally Posted by AJL

If I could get some help on this as soon as possible, that would be great.

...

Hello, AJL,

I#ve found another way to solve your problem nr. 4 :

$\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{4}\right)...\left(1-\frac{1}{n}\right)$ =

$\left(\frac{1}{2}\right)\left(\frac{2}{3}\right)\l eft(\frac{3}{4}\right)...\left(\frac{n-1}{n}\right)$

Now you can cancel denominators and numerators except the first "1" and the last "n" which gives you the RHS of your equation.

EB

Thread: A Bit Of Help Please. Induction Arguments

LinkBack

Thread Tools

Display

A Bit Of Help Please. Induction Arguments

nr. 4 only

Similar Math Help Forum Discussions

arguments for the distribution

Combinatorial arguments

Help... proving arguments.!!!

Please help translate these arguments.....

Arguments and Logarithms...