95 lines
1.9 KiB
Text
95 lines
1.9 KiB
Text
#import "@youwen/zen:0.1.0": *
|
|
|
|
#show: zen.with(
|
|
title: "Homework 5",
|
|
author: "Youwen Wu",
|
|
)
|
|
|
|
#set heading(numbering: none)
|
|
#show heading.where(level: 2): it => [#it.body.]
|
|
#show heading.where(level: 3): it => [#it.body.]
|
|
|
|
#set par(first-line-indent: 0pt, spacing: 1em)
|
|
|
|
|
|
Problems:
|
|
|
|
2.4: \#4bcde, 5ajq, 6ce, 7a, 9, 10, 12abc
|
|
|
|
2.5: \#1abc, 3, 10
|
|
|
|
#outline()
|
|
|
|
= 2.4
|
|
|
|
== 4
|
|
|
|
=== b
|
|
|
|
$3 + 11 + 19 + dots.c + (8n - 5) = 4n^2 - n$
|
|
|
|
First we show the base case for $n = 1$.
|
|
|
|
$ 3 = 4 (1^2) - 1 = 3 $
|
|
|
|
Now we proceed by induction. Assume $sum _(k=1) ^n (8k-5) = 4(n^2) - n$.
|
|
|
|
$
|
|
sum_(k=1)^(n+1) (8k-5) &= 4((n+1)^2) - (n+1) \
|
|
(sum_(k=1)^(n) (8k-5)) + (8(n+1) - 5) &= 4(n^2 + 2n + 1) - n-1 \
|
|
(sum_(k=1)^(n) (8k-5)) + 8n + 3 &= 4n^2 - n + 8n + 3 \
|
|
(sum_(k=1)^(n) (8k-5)) &= 4n^2 - n \
|
|
$
|
|
|
|
and we know that this is true by our original assumption. So by the PMI, this
|
|
is true $forall n in NN$.
|
|
|
|
=== c
|
|
|
|
$sum_(i=1)^n 2^i = 2^(n+1) - 2$
|
|
|
|
For the base case:
|
|
|
|
$ 2^1 = 2(1 + 1) - 2 \ 2 = 2 $
|
|
|
|
Assume that
|
|
|
|
$
|
|
sum_(i=1)^n 2^i = 2^(n+1) - 2
|
|
$
|
|
|
|
Proceeding by induction,
|
|
|
|
$
|
|
sum_(i=1)^(n+1) 2^i = 2^(n+1+1) - 2 \
|
|
(sum_(i=1)^(n) 2^i) + 2^(n+1) = 2^(n+2) - 2 \
|
|
(sum_(i=1)^(n) 2^i) = 2^(n+2) - 2^(n+1) - 2 \
|
|
(sum_(i=1)^(n) 2^i) = 2^(n+1) dot (2 - 1) - 2 \
|
|
(sum_(i=1)^(n) 2^i) = 2^(n+1) - 2 \
|
|
$
|
|
|
|
So by the PMI, it holds for all $n in NN$.
|
|
|
|
=== d
|
|
|
|
$1 dot 1! + 2 dot 2! + 3 dot 3! + dots.c + n dot n! = (n + 1)! - 1$
|
|
|
|
For the base case: $1 dot 1! = (1 + 1)! - 1 \ 1 = 1$
|
|
|
|
Assuming the inductive hypothesis,
|
|
|
|
$
|
|
sum^n_(k=1) k dot k! = (n + 1)! - 1 \
|
|
$
|
|
|
|
Now we proceed by induction
|
|
|
|
$
|
|
sum^(n+1)_(k=1) k dot k! = (n + 2)! - 1 \
|
|
sum^(n)_(k=1) k dot k! + (n + 1) dot (n+1)! = (n + 2) dot (n + 1)! - 1 \
|
|
sum^(n)_(k=1) k dot k! = (n + 2) dot (n + 1)! - (n + 1) dot (n+1)! - 1 \
|
|
sum^(n)_(k=1) k dot k! = (n + 1)! dot (n+2 - (n + 1) - 1 \
|
|
sum^(n)_(k=1) k dot k! = (n + 1)! - 1 \
|
|
$
|
|
|
|
So by the PMI, this is true for all $n in NN$
|