Induction (Need help with understanding notation)

256 Views Asked by At

The image attached below is a problem on induction, the proof has been included. I am enquiring if anyone could explain line for line what the proof states with its notation ( the notation is new to me). (I have a bit of experience with proof by induction, but is stumped by this problem)

Link to the Image

2

There are 2 best solutions below

0
On

The proof is by strong induction. The first line defines $P_n$. The second line is the base case. It shows that $P_n$ holds for $n=1$. The third line is the assumption. The third line assumes that the proposition is true for all $n < k +1$. The next few lines demonstrate the proof. These are the statements in the proof which use the assumption. It has been shown that the LHS is less than $|z_1| + |z_2| + \cdots + |z_{k+1}|$ which is the RHS. Thus the proposition has been proved.

0
On

Okay it seems that you are just new to induction, I'll try to explain it though i assume the internet is full of explanations for it,

Induction is a way for one to conclude a general fact, and it is used when you can solve small parts of a problem, the common known induction is regarding a natural number and this is what being used in the picture you refereed,

The simplest and most common form of mathematical induction infers that a statement involving a natural number n holds for all values of n. The proof consists of two steps:

The basis (base case): prove that the statement holds for the first natural number n. Usually, n = 0 or n = 1, rarely, n = –1 (although not a natural number, the extension of the natural numbers to –1 is still a well-ordered set).

The inductive step: prove that, if the statement holds for some natural number n, then the statement holds for n + 1. The hypothesis in the inductive step that the statement holds for some n is called the induction hypothesis (or inductive hypothesis). To perform the inductive step, one assumes the induction hypothesis and then uses this assumption to prove the statement for n + 1.

Whether n = 0 or n = 1 depends on the definition of the natural numbers. If 0 is considered a natural number, as is common in the fields of combinatorics and mathematical logic, the base case is given by n = 0. If, on the other hand, 1 is taken as the first natural number, then the base case is given by n = 1.

https://en.wikipedia.org/wiki/Mathematical_induction

at your picture, the claim $p_n$ is denoted by : for any $z_1 ,...z_n \in \mathbb C$ it exists that:

$|z_1 +...+z_n|\leq |z_1|+...+|z_n|$

to prove this by induction, you need to prove that it holds for n=1 (the induction base), meaning prove $p_1$, which is: "for any $z\in \mathbb C$ it exists that $|z|\leq|z|$" this is a trivial claim.

than you need to prove (inductive step) that $p_n \Rightarrow p_{n+1}$

meaning, that if we assume that the claim is correct for n complex numbers, than it is correct for n+1 complex numbers, this is the part where you must be able to "solve the smaller problem", i assume that when they mention (a), they mention a separate exercise in which you had to prove the triangle inequality which claim that for any 2 complex numbers $z_1 , z_2$ we get that $|z_1 + z_2|\leq |z_1|+|z_2|$

than lets denote $z_1 +...+z_n = w$ as $w\in \mathbb C$ we get that by the triangle inequality:

$|z_1+...+z_n+z_{n+1}|=|w+z_{n+1}|\leq |w|+ |z_{n+1}|$

and than by the induction hypothesis (meaning, we assume that $p_n$ is correct, we get that:

$|w|=|z_1+...+z_n|\leq |z_1|+...+|z_n|$

and at the overall we got that:

$|z_1+...+z_n+z_{n+1}|=|w+z_{n+1}|\leq |w|+ |z_{n+1}| \leq |z_1|+...+|z_n|+ |z_{n+1}|$

thus we managed to prove that $p_n \Rightarrow p_{n+1}$ and then by the axiom of induction we get that $p_n$ holds for every natural number $n\in \mathbb N$