For questions about mathematical induction, a method of mathematical proof. Mathematical induction generally proceeds by proving a statement for some integer, called the *base case*, and then proving that if it holds for one integer then it holds for the next integer. This tag is primarily aimed ...

learn more… | top users | synonyms

2
votes
2answers
44 views

Proving with induction $(1-x)^n<\frac 1 {1+nx}$

Prove using induction that $\forall n\in\mathbb N, \forall x\in \mathbb R: 0<x<1: (1-x)^n<\frac 1 {1+nx}$ My attempt: Base: for $n=1: 1-x<\frac 1 {1+x}\iff 1-x^2<1$, true since ...
1
vote
2answers
40 views

Show if $0 \le a <b$ implies $0 \le a^{\frac{1}{n}}<b^{\frac{1}{n}}$

Given that $0\le a<b$ show that $0\leq a^{1/n}<b^{1/n}$ Is this proof by induction? Show it's correct for $n=1$ Assume true for $n=k$, then $0\leq a^{1/k}<b^{1/k}$ holds for some $k$, ...
1
vote
3answers
60 views

Use induction to prove that sum of the first $2n$ terms of the series $1^2-3^2+5^2-7^2+…$ is $-8n^2$.

Use induction to prove that sum of the first $2n$ terms of the series $1^2-3^2+5^2-7^2+…$ is $-8n^2$. I came up with the formula $\displaystyle\sum_{r=1}^{2n} (-1)^{r+1}(2r-1)^2=-8n^2$ but I got ...
0
votes
0answers
10 views

Proof for Determinants using Laplace and induction.

Matrix $A = (a_{ij}) \in M (n x n, Field)$, Matrix $B = ((-1)^{i+j}a_{ij})$ I need to prove that det(A)=det(B). I thought induction might be one solution, but I don't know how to apply the Laplace ...
1
vote
2answers
36 views

Induction proof concerning Pell numbers

Problem: The Pell numbers $p_n$ are defined by the recurrence relation \begin{align*} p_{n+1} = 2p_n + p_{n-1} \end{align*} for $n \geq 1$, together with $p_0 = 0$ and $p_1 = 1$. Prove with ...
1
vote
1answer
24 views

Inverse of a product in a group can be written as the product of the inverses of each element in reverse order

Let $(G,\circ)$ be a group and let $g_1,...,g_n\in G, n\in\aleph$. Prove that $(g_1\circ ...\circ g_n)^{-1}=g_n^{-1}\circ ...\circ g_1^{-1}$ I tried this by induction but was unsure how to take out ...
3
votes
1answer
79 views

How is induction justified in intuitionistic logic?

This question might be extremely naïve for which I apologise in advance. The induction principle can be stated as: If $A ⊂ ℕ$ such that $1 ∈ A$, and $ν(A) ⊂ A$ (where $ν\colon ℕ → ℕ$ is ...
0
votes
1answer
24 views

Proving the existence of a Bijection between Cartesian Products of Sets by Induction

Prove by induction that for any sets $A_1, \ldots , A_n$, there is a bijection from $(((A_1 \times A_2) \times A_3) \times \ldots \times A_n)$ to $A_1 \times (A_2 \times ( \ldots (A_{n-1} \times A_n) ...
0
votes
1answer
20 views

summation inequality with logarithms

show: $$\sum_{i=1}^n \log_{2}\,i = O(n\log n)$$ Proof by induction: $$\sum_{i=1}^n \log\,i \le n\log n$$ $$\text{Test for n=1: }\sum_{i=1}^1 \log_{2}\,i \le 1\log 1$$ $$0 \le 0\text{ true for ...
0
votes
1answer
37 views

For what natural number $n$ is the following inequality true: $2^n \geq 2\cdot n^2$?

Can you solve this by using induction? The inequality is true for $n = 1$, but is false until $n = 7$. After the induction step I got $$2^n \geq n^2 + 2n + 1.$$ If you take the limit as $n$ ...
1
vote
1answer
12 views

Power of two commuting elements in a group is the binary operation of each of the two elements raised to that power

Let $(G,\ast)$ be a group and let $n\in\aleph$. Prove that if g, h $\in G$ commute, then $(g\ast h)^n$=$g^n\ast h^n$
3
votes
1answer
52 views

Proof that $\sum_{i=1}^n{1} = n$ for all $n \in \Bbb Z^+$

It seems obvious that $$\forall n \in \Bbb Z^+, \sum_{i=1}^n{1} = n $$ However, I'm having trouble coming up with a formal proof for this. Given a concrete number like $4$, we can say that ...
0
votes
2answers
27 views

proof by induction summation inequality

show by induction that: $$\sum_{i=1}^n i^2 = O(n^3)$$ what I have so far: $$\sum_{i=1}^n i^2 <= n^3$$ base case: for n=1 $$\sum_{i=1}^1 i^2 <= 1^3$$ ...
0
votes
0answers
18 views

Practicing mathematical proofs in preparation for another course and could use some help [on hold]

I'm starting a course on Algorithms and the professor wants to test our induction and proof knowledge. Problem is, our prerequisite courses never focused on such material. I'm hoping someone could ...
3
votes
1answer
42 views

How to prove that calculating Ackermman function stops?

Let $$\begin{eqnarray*} A(0,y) &=& y+1 \\ A(x+1,0) &=& A(x,1) \\ A(x+1,y+1) &=& A(x,A(x+1,y)) \end{eqnarray*}$$ be Ackermann function. How to prove by structural induction ...
0
votes
1answer
11 views

Cantor Set and Base 3 Decimal Expansions

I'm trying to show that every point in the Cantor Set (obtained by "middle-thirds" removal, starting with $[0,1]$) has a base 3 decimal expansion consisting of only zeros and twos. I think the proof ...
1
vote
1answer
12 views

Proof via strong induction of a string output

I'm still new to the whole proof thing (first class of discrete mathematics and analysis right now). I could do general induction problems, but the fact that 'n' is the output here along with the ...
1
vote
3answers
85 views

Factorial inequality $2!\,4!\,6!\cdots (2n)!\geq\left((n+1)!\right)^n$ using induction

I want to show $2!\,4!\,6!\cdots (2n)!\geq\left((n+1)!\right)^n.$ Assume that it holds for some positive integer $k\geq 1$ and we will prove, $2!\,4!\,6!\cdots (2k+2)!\geq\left((k+2)!\right)^{k+1}$. ...
1
vote
1answer
26 views

Proof of the second principle of mathematical induction

This was an exercise in my lecture notes for which no answer was provided, so I seek verification on whether my proof is correct. Prove that if 1. $P(n_0)$ is true for some $n_0 \in \mathbb N$, and ...
2
votes
3answers
114 views

Help with the algebra in for this number theory proof?

For all $n\geq 1$, prove with mathematical induction $\frac{1}{1^2}+\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{n^2}\leq 2-\frac{1}{n}$ So far.. I have substituted 1 and saw that the statement is ...
2
votes
4answers
101 views

Proving $4^n > n^4$ holds for $n\geq 5$ via induction.

I know that it holds for $n=5$, so the first step is done. For the second step, my IH is: $4^n > n^4$, and I must show that $4^{n+1} > (n+1)^4$. I did as follows: $4^{n+1} = 4*4^n > 4n^4$, ...
33
votes
18answers
6k views

Examples of mathematical induction

What are the best examples of mathematical induction available at the secondary-school level---totally elementary---that do not involve expressions of the form $\bullet+\cdots\cdots\cdots+\bullet$ ...
0
votes
1answer
41 views

prove by mathematical induction

I've been trying to solve this but I'm having trouble in simplifying it, in order to match the right hand side. Could you solve this? $$\sum_{i=1}^{n+1} i\cdot 2^i = n\cdot 2^{n+2} +2 ,$$ for all ...
0
votes
3answers
75 views

Proof of an inequality by induction

Let $n \in \mathbb N^+$. Show that if $x_1, x_2, ... , x_n$ are $n$ real numbers such that $-1 \le x_i \le 0$ for each $1 \le i \le n$, then $$(1 + x_1)(1 + x_2)...(1 + x_n) \ge 1 + x_1 + x_2 + ... + ...
0
votes
0answers
59 views

On correctness of induction proof

I want to prove a certain property $\mathsf{P}$ on every multiaffine polynomial in $\Bbb R[x_1,x_2,\dots,x_{n-1},x_n]$. Supposing I show property $\mathsf{P}$ to be valid at $n\geq9$ variable ...
3
votes
2answers
35 views

Proving $1+\sum_{i=1}^n i (i!)=(n+1)!$ [duplicate]

How would you prove the following using induction. n is a non negative integer $$1+\sum_{i=1}^n i i!=(n+1)!$$ This be what I did base case let $n=3$ $$1+1+4+18=(3+1)!$$ $24=24$ Hypothesis step ...
2
votes
1answer
22 views

Height of quasi-complete binary tree

Let us define a quasi-complete binary tree as a rooted binary whose nodes have all two children except at most those of the penultimate level, which can have either one or two children. I read that ...
4
votes
0answers
58 views

Prove $\forall n\in\mathbb{N}, \exists m\in\mathbb{N}; n=\pm1^2\pm2^2\pm\cdots\pm m^2.$

And we choose the positive and negative signs in a way that the equation becomes true. I think it can be proved with mathematical induction. So here's how I begin: For $n=1$, $1=+1^2$ which is true. ...
0
votes
0answers
18 views

What is the difference between assuming for $\forall k< n$ and proving for $n$ than assuming for $n$ and proving for $n+1$

What is the difference between assuming for $\forall k< n$ and proving for $n$ than assuming for $n$ and proving for $n+1$ (or $n-1$ and proving for $n$)? both with induction. The first one is ...
3
votes
2answers
1k views

Proof the inequality $n! \geq 2^n$ by induction

I'm having difficulity solving an exercise in my course. The question is: Prove that $n!\geq 2^n$. We have to do this with induction. I started like this: The lowest natural number where the ...
3
votes
2answers
73 views

Divisibility Of Positve Integers [closed]

Suppose a,b and c are three positive integers which satisfy the condition that ($a$2+$b$2+$c$2) is divisible by $(a+b+c)$. Prove that there exists infinitely many positive integers $n$ for which ...
2
votes
3answers
54 views

Proof by induction, binomial coefficient

I have to make the following proof: $${\sum\limits_{k=1}^n}{k}{n\choose k} = n2^{n-1}$$ Base case, $n = 1$: $${\sum\limits_{k=1}^{1}}{k}{1\choose k} = 1 = 1\cdot2^0=1$$ Inductive Hypothesis: for ...
0
votes
4answers
45 views

I'm having trouble understanding a step of induction.

The problem my teacher presented was to prove, $(1 + x)^n \geq 1 + nx$ for all real numbers $x > -1$ and integers $n \geq 2$. The way it was done in class is: $(1+nx)(1+x) ≤ (1+x)^n (1+x) $ ...
-1
votes
1answer
24 views

Ordering of real numbers compatible with n-th powers/reciprocal powers (induction)

I have to use induction to prove that $$0 \leq a < b \implies 0 \leq a^n < b^n$$ for all natural n. Also (perhaps very similarly) that $$0 \leq a < b \implies 0 \leq a^{1/n} < b^{1/n}.$$ ...
0
votes
1answer
39 views

Formal Method for Determining the Domain of Solutions to an Equation?

     I'm doing an algebra review packet in order to prepare to take an independent-study calculus class. About five eighths of the way through the problems posed by this ...
1
vote
5answers
104 views

how to prove: $\sum\limits_{k=1}^n k\binom{n}{k}=n \cdot 2^{n-1} $ [duplicate]

need help to prove this: $\sum\limits_{k=1}^n k\binom{n}{k}=n \cdot 2^{n-1} $ where $n$ is integer $\geq 1$. Question also said taking the derivative of $(1 + x)^n$ would be helpful which I've found ...
0
votes
1answer
24 views

Prove that all elements in the set T is divisible by 3 using structural induction.

Let T be the set defined recursively as follows: (1) (0,3) $\in$ T (2) If (x, y) $\in$ T, then (x + 2, y - 1) $\in$ T and (x - 3, y) $\in$ T. (3) Every element of T can be obtained from (1) by ...
0
votes
1answer
21 views

Two recurrence relations gcd proof

Let $q_1, q_2,\ldots$ be a sequence of integers with $q_i\gt0$ for all $i\gt 1$. Define $(a_n)_{n\ge-1}$ and $(b_n)_{n\ge-1}$ by the following recurrence relations: $a_{-1}=0,\ a_0=1,\ b_{-1}=1,\ ...
1
vote
2answers
136 views

Using the Invariant Principle to prove a coordinate can't be reached

Problem: A robot wanders around a 2-dimensional grid. Starting at $(0, 0)$, he is allowed 4 different kinds of steps: $(+2, -1)$ $(+1, -2)$ $(+1, +1)$ $(-3, 0)$ He is trying to get to $(0, 2)$. ...
1
vote
3answers
350 views

Help with Induction problem?

I'm not sure where to start on this induction problem. Problem: A group of $n \geq 1$ people can be divided into teams, each containing either 4 or 7 people. What are all possible values of $n$? Use ...
0
votes
0answers
24 views

Geometric interpretation or solution of an induction problem

Problem: Suppose you begin with a pile of $n$ stones and split this pile into $n$ piles of one stone each by successively splitting a pile of stones into two smaller piles. Each time you split a pile, ...
1
vote
7answers
50 views

Induction proof of $1 + 6 + 11 +\cdots + (5n-4)=n(5n-3)/2$

I need help getting started with this proof. Prove using mathematical induction. $$ 1 + 6 + 11 + \cdots + (5n-4)=n(5n-3)/2 $$ $$ n=1,2,3,... $$ I know for my basis step I need to set $n=1$ but I ...
1
vote
0answers
112 views

using induction to prove that the formula for finding the n-th term of the Fibonacci sequence is: [duplicate]

May someone help me? I am trying to use induction to prove that the formula for finding the $n^{th}$ term of the Fibonacci sequence is: ...
1
vote
2answers
104 views

Inductive proof of a formula for Fibonacci numbers

May someone help me? I am trying to use induction to prove that the formula for finding the $n$-th term of the Fibonacci sequence is: ...
3
votes
1answer
59 views

Induction proof about entries of powers of strictly upper triangular matrix

Let $A$ be a $n \times n$ strictly upper triangular matrix. Prove that, for $k \ge1$, the matrix $A^k$ has the property that $(A^k)_{i,j} = 0$ for all $(i,j)$ with $j-i < k$. Also, show that $A^n ...
2
votes
3answers
183 views

Statement on the Fibonacci sequence

Question: Let $n,m,\in\mathbb{N^*}$ with $n>1$ and let $u_n$ denote the $n$-th term of the Fibonacci sequence, then $$u_{n+m}=u_{n-1}u_m+u_nu_{m+1}$$ I know these theorems: Two consecutive ...
0
votes
3answers
41 views

simple proof by induction exercise - beginner

I am rather illiterate when it comes to mathematics, I am afraid. In an effort to change that, I grabbed a copy of 'What is mathematics? : An elementary approach to ideas and methods' and have already ...
0
votes
2answers
40 views

Trouble solving this induction problem

Show that, for every $n\ge2$, $3^n >n(n-1)$. Well, I started by showing the base case ($n = 2$): $3^2 > 2$ Now, for $n+1$: $P(n)\Rightarrow P(n+1)$ $$3^{n+1} > (n+1)n$$ My ...
-2
votes
0answers
57 views

Prove by induction the $n$th derivative [closed]

Let $f(x) = \ln(1+x)$. Prove by induction that, for $n \geq 1$, $$ f^{(n)}(x) = (-1)^{(n-1)}\cdot \frac{(n-1)!}{(1+x)^n}. $$ How do I go about proving this? I have done the n=1 base step to show it ...
0
votes
2answers
47 views

If $d$ divides $k$ and $d$ divides $n$, then $d$ divides $(8k - 3n)$

Suppose that $k$, $n$, and $d$ are integers and $d$ is not $0$. Prove: If $d$ divides $k$ and $d$ divides $n$, then $d$ divides $(8k - 3n)$. You may not use the theorem stating the following: Let ...