1. ## A Bit Of Help Please. Induction Arguments

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 )

2. Hello, AJL!

Here's the first one . . .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

If you know modular Mathematics:

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

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

-Dan

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

For n = 1:
$\displaystyle \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
$\displaystyle \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 $\displaystyle \frac{k}{k+1}$ according to assumption, so we need to show
$\displaystyle \frac{k}{k+1} + \frac{1}{(k+1)(k+2)} = \frac{k+1}{k+2}$

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

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

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

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

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

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

-Dan

5. 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

6. 6) $\displaystyle 2n+1 < 2^n$

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

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

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

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

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

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

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

-Dan

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

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

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

So assume this is true for n = k.

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

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

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

-Dan

8. Hello again, AJL!

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

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

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

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

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

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

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

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

9. ## nr. 4 only

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 :

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

$\displaystyle \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