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 )
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.
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
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}$
As advertised.
-Dan
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) 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)!$
as advertised.
-Dan
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.$
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