01204211/activity3 induction 1

This is part of 01204211-58

In-class activities 3

A.1 (LPV) Prove that for any integer $k\geq 1$, we have that

$1+3+\cdots +(2k-1)=k^{2}$.

In problem A.1, you have to state clearly the property $P(k)$ that you want to prove. Note that we use variable $k$ in the statement, to avoid confusion, you should choose other variables when you work on the inductive step.

A.2 (MN) Prove that for any integer $n\geq 0$, the following formula is true:

$\sum _{i=0}^{n}2^{i}=2^{n+1}-1$.

In problem A.2, you have to state clearly the property $P(n)$ that you want to prove.

A.3 (MN-ex-1b) Prove that for integer $n\geq 1$,

$\sum _{i=1}^{n}i\cdot 2^{i}=(n-1)2^{n+1}+2.$

A.4 (R-3.3-ex-12) Prove that $3^{n}<n!$ whenever $n$ is a positive integer greater than 6.

A.5 (a*) Prove using induction that using only 2-baht coins and 3-baht coins, one can obtain $n$ baht for $n\geq 4$. (Do not use strong induction.)

(b) Also prove this statement without using induction.

A.6 (MN-ex-3a) Draw $n$ lines in the plane in such a way that no two are parallel and no three intersect in a common point. How many parts do the lines divide the plane into? Experiment, guess the value, and prove it by induction.

Homework 3

Due: 23:59 18 Sept 2015 16 Sept 2015

H.1 (LPV-2.1.5) Prove the following identity:

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

H.2 (LPV-2.5.4b) Prove that for any integer $n\geq 1$, $n^{3}-n$ is a multiple of 6.

H.3 (R-3.3-ex-6) Find the formula for

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

Try a few values of $n$, guess the formula, and prove it by induction.

H.4 (R-3.3-ex-19) Show that using only 3-baht coins and 5-baht coins, one can form a set of coins worth $n$ baht for any integer $n>7$.

H.5* (R-3.3-ex-37) Show that if $n$ is a positive integer then

$\sum _{\{a_{1},a_{2},\ldots ,a_{k}\}\subseteq \{1,2,\ldots ,n\}}{\frac {1}{a_{1}a_{2}\cdots a_{k}}}=n$.

In this problem, the sum is over all nonempty subsets of $\{1,2,3,\ldots ,n\}$.