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 meant ...

learn more… | top users | synonyms

0
votes
2answers
28 views

$n$ points on a circle connect by lines, the sum of the internal angles is $(n - 1) 180$°

I am trying to understand a proof by induction on a geometry problem: For all $n\geq 3$, if $n$ distinct points on a circle are connected in consecutive order by straight lines, then the ...
1
vote
1answer
73 views

Using induction for sequences defined by recursion, such as $a_{n+1} = \frac14(a_n^2 +3)$

Let the sequence $\{a_n\}$ be defined by $a_{n+1} = \frac14(a_n^2 +3)$. We want to prove that if the first term $a_1$ is between $0$ and $1$ then the sequence converges. My question is why do we ...
5
votes
1answer
110 views

Inequality with sum of Binomial coefficients.

Prove that for every positive integer $n \ge 2$$$\sum^n_{k=1}k \sqrt{\begin{pmatrix}n\\ k\end{pmatrix}}\leq\sqrt{2^{n-1}n^3}$$ I tried it by induction but I didn't know how to end it.
3
votes
2answers
96 views

Prove the empty set is a subset of every set. Does induction work?

I've taken a look at the proofs by contrapositive and by vacuous truths (for the above title), but I was wondering whether or not the following proof by induction works. The following proof proceeds ...
5
votes
4answers
67 views

How to proof that $\sum_{i=1}^{2^n} 1/i \ge 1+n/2$

I had troubles trying to prove that for every $n\ge1$ $$\sum_{i=1}^{2^n}\frac1i\ge 1+\frac n2$$ Can you give me a hint about the induction proof or show me in detail how can I prove it? I would ...
2
votes
1answer
36 views

Proving by induction $3^{n-2}\le(n-1)! : \forall n\ge 6$

Prove by induction: $3^{n-2}\le(n-1)! : \forall n\ge 6$ The base case and hypothesis are trivial, we want to show that: $3^{n-1}\le(n)! : \forall n\ge 6$, but I get stuck very early: $3^{n-1}\le ...
3
votes
1answer
51 views

Simplexes in $\mathbb R^n$ have at most $n+1$ points

This is an exercise from the book Espaços Métricos (metric spaces) by Elon Lima. I'm translating it (the part of it that I'm having trouble with): Show that if $X\subset\mathbb R^n$ is such that ...
0
votes
1answer
258 views

strong induction example

There is following example given in a book. I am not sure how do we conclude that $a$ is divisible by prime? See this section: Case 2 ($k + 1$ is not prime): In this case $k+1=ab$ where $a$ and ...
3
votes
3answers
115 views

${n \choose k}\leq n^k$

Let $n$ et $k\in \mathbb{N}$ such that : $k\leq n $ Show that :$${n \choose k}\leq n^{k}$$ My thoughts: note that for all $\ k\leq n$ : $${n \choose k}=\frac{n!}{k!(n-k)!}$$ To prove ...
1
vote
2answers
32 views

Prove by induction that $\forall n \in \mathbb{N} \cup \{0\}: \sum_{k=0}^{n} \frac{k}{2^{k}} = 2 - \frac{n + 2}{2^{n}}$

Prove by induction $\forall n \in \mathbb{N} \cup \{0\}: \sum_{k=0}^{n} \frac{k}{2^{k}} = 2 - \frac{n + 2}{2^{n}}$ Step 1: Show true for n = 0: LHS: $\frac{0}{2^{0}}$ = 0 RHS = $2 - ...
1
vote
1answer
29 views

Prove by induction that $\sum_{k=0}^{n}(-1)^{n+k} k^{2} = \frac{n(n+1)}{2}$

Prove by mathematical induction that $\forall n \in \mathbb{N}:~~~~ \sum_{k=0}^{n}(-1)^{n+k} k^{2} = \frac{n(n+1)}{2}$ Step 1: Show true for $n = 1$: LHS: $(-1)^{(1+0)} \cdot 0^{2} + (-1)^{(1+1)} ...
1
vote
2answers
88 views

Simplify sum of factorials with mathematical induction

I want to prove with mathematical induction that: $$\sum_{i=1}^n i \cdot i! = (n+1)! - 1$$ So in the first step we define $n = 1$: $$\sum_{i=1}^1 i \cdot i! = 1 \cdot 1! = 1 = 2! - 1$$ In the ...
1
vote
3answers
57 views

Prove that if a set A of natural numbers contains $n_0$ and whenever A contains k it also contains k+1.

Prove that if a set A of natural numbers contains $n_0$ and that whenever A contains k it also contains k+1. Prove that A contains all natural numbers $ \geq n_0 $ This is rather similar to a ...
0
votes
1answer
115 views

Prove Bernoulli inequality if $h>-1$

Qi) Prove Bernoulli's inequality If $h> -1$, then $ (1+h)^n \geq 1+nh$ Qii) why is this Trivial is $h>0 $ Something i have always been lucky with is having a lot of intuition to go on with ...
0
votes
1answer
30 views

Is this inductive proof valid?

Show that $n!>3^n$ for $n \ge 7$ My attempt: Let the statement $P_n$ say that $n!>3^n$. Base Case Let $n=7$, then $P_7$ says that $7! > 3^7 \implies 5040>2187$ Inductive Step Fix $k ...
1
vote
1answer
48 views

induction, recursive function, discrete mathematics

Please help solve following recursive function. How can I solve $n-10$ for $M(99)$ or $M(98)$ if $n>100$ ? : Find $M(99), M(100)$, and $M(98)$ when $$ M(n) = \begin{cases} n-10, & ...
1
vote
1answer
51 views

Write $(1^3 −1)−(2^3 −1)+(3^3 −1)−(4^3 −1)+(5^3 −1)$ using summation or product notation.

Question: Write the following using summation or product notation: $$(1^3 −1)−(2^3 −1)+(3^3 −1)−(4^3 −1)+(5^3 −1)$$ I have got following conversion, however it looks a bit over complicated: ...
3
votes
3answers
91 views

How to prove $\sum_{k=1}^{n}k\binom{n}{k} = n2^{n-1}$ [duplicate]

$\sum_{k=1}^{n}k\binom{n}{k} = n2^{n-1}$ I have tried both induction and transforming both sides to get equality but no luck I know that $\sum_{k=1}^{n}\binom{n}{k} = 2^{n}-1$ and ...
5
votes
1answer
60 views

Show that $(1+a_1x+\ldots+a_rx^r)^k=1+x+x^{r+1}q(x)$

Fixed $k\ge 1$. Show that for each $r$, you can find $a_1,\cdot\cdot\cdot,a_r\in \mathbb{F}$ such that :$$(1+a_1x+\cdot\cdot\cdot+a_rx^r)^k=1+x+x^{r+1}q(x)$$ where $q(x)$ is a polynomial. Any ...
1
vote
1answer
101 views

Strong induction. What is responsible for basis step?

I have no problems with weak induction. There is a basis step and inductive step. But it seems that basis step is missing in the strong induction. It says that$$(\forall n[ \forall m<n, ...
3
votes
0answers
60 views

Using induction to prove a congruence?

Let $a = 2+\sqrt{3}.$ By analogy to complex numbers let R$(a)$ be $r,$ the non-surd part of $r + s\sqrt{3}.$ I would like to show that a necessary but by no means sufficient condition that ...
5
votes
3answers
164 views

Proving inequality $\frac{n}{2} < 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + … + + \frac{1}{2^{n}-1} < n$

Prove the inequality $\frac{n}{2} < 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + ... + + \frac{1}{2^{n}-1} < n$ where $n\in\mathbb{N}\backslash\{0,1\}$ My work At first I tried ...
0
votes
0answers
50 views

Induction: Fibonacci / Lucas Numbers [duplicate]

From Andrews' Number Theory, Chapter 1, Section 1, Problem 15: Prove, by induction, that $F_{2n} = F_nL_n$ where $F_n$ denotes the nth Fibonacci number and $L_n$ denotes the nth Lucas ...
0
votes
1answer
43 views

Proving that $\sum_{i=0}^{n-p} \frac{i!}{(p+i)!} = \frac{1}{p-1}[\frac{1}{(p-1)!}-\frac{(n-p+1)!}{n!}]$

I'm trying to prove that $$\sum_{i=0}^{n-p} \frac{i!}{(p+i)!} = \frac{1}{p-1}\left[\frac{1}{(p-1)!}-\frac{(n-p+1)!}{n!}\right]$$ for $p,n \geq 2$, $p, q \in \mathbb{N}$. I'm trying to use induction ...
0
votes
1answer
101 views

Cauchy convergence criterion for the sequence $x_{n+1}=\frac{x_n+x_{n-1}}{2}$ [closed]

Suppose $x_0$, $x_1$ are arbitrary and a sequence $(x_n)$ be defined by $x_{n+1}=\frac{x_n+x_{n-1}}{2}, n\geq 1.$ I want show, by induction, the following: $x_0\leq x_n\leq x_1,\forall n\geq 1$; ...
24
votes
4answers
2k views

Why is “mathematical induction” called “mathematical”?

One of my whims is that I never write "mathematical induction" but just "induction". We are doing maths, so what is the point about precising? We don't say "Let $f$ be a mathematical function from the ...
2
votes
2answers
86 views

Understanding the proof that the sum of the first $n$ natural numbers is $\frac{1}{2}n(n+1)$ [duplicate]

I'm reading the following book: http://www.cs.princeton.edu/courses/archive/spring10/cos433/mathcs.pdf. In page 26, they attempt to prove the following theorem using Induction: For all $n \in ...
4
votes
3answers
230 views

Inequality of the Fibonacci sequence and the golden ratio

How can I prove that for each $n\in\Bbb Z^+$ $$\frac{f_{2n}}{f_{2n-1}}\leq\frac{1+\sqrt{5}}{2}$$ where each $f_i$ is a term of the Fibonacci sequence. Any help is really appreciated
1
vote
3answers
74 views

Induction on nth polynomial proof.

Question: Prove by induction that $ 1+r+r^2+\cdots+r^n = \dfrac {1-r^{n+1}} {1-r} $ where $ r \in \mathbb{R} $ When $n$ is odd, this is really easy as the right side breaks down to $\dfrac ...
2
votes
3answers
86 views

Tips on constructing a proof by induction.

So right now I'm working on a discrete mathematics course and I've been having a bit of trouble figuring out how to prove certain equations using mathematical induction. I have very little trouble ...
0
votes
4answers
150 views

How to prove that the sum of squared binomials equals $\binom{2n}{n}$ [duplicate]

I've stumbled upon this lemma a few times in my textbook: $$\sum_{k=0}^{n}\begin{pmatrix}n\\k\end{pmatrix}^2=\begin{pmatrix}2n\\n\end{pmatrix}$$ I've been trying to prove it, but I simply can't seem ...
0
votes
3answers
84 views

Induction proof that $2^m 2^n = 2^{m+n}$

I am unable to proceed with the below claim. $$2^{m} \times 2^{n} = 2^{m+n}$$ Could anyone let me know how to prove the above claim using induction proof? I was able to derive proof for odd natural ...
1
vote
1answer
34 views

Question around the following relation: $T(n,1) = n$, for a positive integer $n$, and for all $k\geq 1,\ T(n,k+1)=n^{T(n,k)}$.

I'm beginning the studies on number theory and then i'm facing the following problem that i couldn't solve yet: given a positive integer $n$ and being $T(n,1)=n$ and, for all $k\ge1$, ...
0
votes
1answer
55 views

How to prove that $(a+b-ab)^n+(1-a^n)(1-b^n) \geq n $ for $a,b\in [0,1]$ and $n\in\mathbb{N}$?

Let $a,b\in [0,1]$ and $n\in\mathbb{N}$. Prove the following inequality: $$(a+b-ab)^n+(1-a^n)(1-b^n) \geq n $$ I thought on using M Induction: Assuming that the inequality holds for $n=k,$ ...
0
votes
2answers
56 views

A simple mathematical induction proof.

Let n be a natural number, and let $ f:\{ i \in \mathbb{N} : 1 \le i \le n\} \rightarrow\mathbb{N} $ be a function. Show that there exists a natural number M such that $f(i) \le M $ for $1 \le i \le ...
1
vote
4answers
62 views

How to prove this equation by induction?

I am trying to prove this equation by mathematical induction $$f_{n+1}f_{n-1} = f_{n}^{2}+(-1)^n$$ is true where $f_{n} = $ the nth number in the Fibonacci sequence. I don't quite get how to do this ...
1
vote
3answers
82 views

Want to ensure my proof is rigourous enough.

Question. Prove: $ 0 \leq x < y $ then $ x^n < y^n$ $ \forall n \in \mathbb{N} $ I'm particularly bad at proving obvious things but here it goes. ( please be super strict on analyzing my proof ...
1
vote
1answer
91 views

Induction and basic assumptions in Graph Theory

I am beginning to work through a text in graph theory and have a couple of questions. 1) Can we always assume a graph is nonempty, i.e., if a graph $G$ has order $n$, do we assume $n\in \{1,2,...\}$? ...
3
votes
1answer
82 views

Writing a proof of the convergence of a series defined recursively

Define the sequence $a_n$ recursively by $a_1=1$ and $$a_{n+1}=\frac13\left(a_n^2+\frac1n\right)$$ (a) Prove, by induction or otherwise, that $(a_n)$ is decreasing. (b) Prove that the series ...
1
vote
2answers
48 views

Prove the inequality $(n+1)^4 < 4n^4$ for $n\geq 3$ by induction

The inequality I'm concerned with is $(n+1)^4 < 4n^4,\ n\geq 3$. I'm not sure how induction is supposed to work here. If I assume $(k+1)^4<4k^4$, I cannot see how this helps show ...
1
vote
3answers
102 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}$. ...
5
votes
1answer
106 views

Proving $\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\cdots+\frac{1}{\sqrt{n}}>2-\frac{2}{n}$ by induction for $n\geq 1$

I have the following inequality to prove with induction: $$P(n): \frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\cdots\frac{1}{\sqrt{n}}>2-\frac{2}{n}, \forall n\in \mathbb{\:N}^*$$ I ...
4
votes
6answers
441 views

Question on induction technique

When one uses induction (say on $n$) to prove something, does it mean the proof holds for all finite values of $n$ or does it always hold when even $n$ takes $\pm\infty$?
1
vote
2answers
127 views

An exercise from Knuth's book - Proving a formula by induction

I would like to find a formula for this sum: $$ \frac{1^3}{1^4+4} - \frac{3^3}{3^4+4} + \frac{5^3}{5^4+4} - ... + \frac{(-1)^n(2n+1)^3}{(2n+1)^4+4} $$ The answer given (Knuth's book, The Art of ...
3
votes
1answer
52 views

Existence of two unrelated pairs in a constrained relation

Given two sets $S, T$ and a relation defined by a set of pairs $R \subset S \times T$, such that: $$ \exists \, s_1, s_2 \in S : s_1 \neq s_2 \\ \exists \, t_1, t_2 \in T : t_1 \neq t_2 \\ ...
3
votes
2answers
67 views

Proving that a function is absolutely monotonic on a given interval

According to the following Wolfram Alpha article: http://mathworld.wolfram.com/AbsolutelyMonotonicFunction.html, the function $f(x) = -\ln(-x)$ is absolutely monotonic on the interval $[-1,0)$. My ...
0
votes
2answers
33 views

Induction proof for $x \le y $

So these are $x \in \{1 ... i\}$ and $y \in \{ i + 1 ... n\}$, for $i, n \in \mathbb N$. I want to prove it for every $x \le y $. I know it`s easy but the solution is escaping me. I have tried with ...
2
votes
1answer
97 views

Number of ways to fill a $2\times n$ grid with $1\times 2$ and $2\times 2$ tiles

How many ways are there to fill a $2\times n$ grid with $1\times 2$ and $2\times 2$ tiles? Rotating is allowed. Progress Let $T_n$ be the number of ways; then $T_n = T_{ n-1} + T_{ n-2} + 1 $ ...
1
vote
0answers
54 views

can anyone prove this with induction?

Suppose that we have a sequence of numbers $x_1,x_2,\ldots,x_n$ called $S$. A subsequence of $S$ is a sequence obtained by omitting some elements of $S$. An increasing subsequence of $S$ called $IS$ ...
3
votes
1answer
107 views

Model of Robinson Arithmetic but not Peano Arithmetic

I am curious how can structure of with linear successor function that do not admin induction looks like. In other words I would like to see structure of Peano Arithmetic without induction. I believe ...