Questions tagged [induction]

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 for questions about induction over natural numbers but is also appropriate for other kinds of induction such as transfinite, structural, double, backwards, etc.

994 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
13
votes
0answers
247 views

Generalization of real induction for topological spaces?

Real induction is a useful proof technique which can be thought as a version of "continuous" induction. I will include here version from Pete L. Clark's text mentioned in this answer,1 where it is ...
9
votes
0answers
429 views

Two (strictly related) proofs by induction of inequalities.

This is a question I originally asked on MSE, receiving no answer, even with a bounty (which expired) on it. Therefore I am crosslinking in order to prevent duplication of effort: see here for the ...
7
votes
0answers
143 views

$f-1$, $f$, $f+1$ cannot be all square

I'm having trouble with the following exercise: Let $k$ be an algebraically closed field with characteristic $\neq 2$, and let $f \in k[X]$. Show that $f-1$, $f$ and $f+1$ are all square only if $f ...
7
votes
1answer
142 views

If in all subsets of size k there exist at least one pair of elements in a relation…

I’ve recently got stuck on a theorem that seems to be true, but I am not sure if I am able to prove it: $\large\forall_{x\in\mathbb{P}_k(\mathbb{N})}\exists_{\left\{ y_1,y_2\right\}\subset x \land ...
7
votes
0answers
15k views

Binomial Theorem Proof by Induction

Did i prove the Binomial Theorem correctly? I got a feeling I did, but need another set of eyes to look over my work. Not really much of a question, sorry. Binomial Theorem $$(x+y)^{n}=\sum_{k=0}^{n}...
6
votes
0answers
164 views

Recursive induction proof

$$𝑡(𝑛) = (𝑛−1)+\frac{𝑛−1}{𝑛^2}⋅\sum_{k=1}^{n-1}t(k)$$ Use induction to prove that $𝑡(𝑛)≤2𝑛$ for all $𝑛≥1$. I have the base case. I got \begin{align} 𝑡(m+1) & = m+\frac{m}{(m+1)^2}⋅\...
6
votes
0answers
1k views

Is there such a thing as “finite” induction?

I am not sure of the terminology that I am looking for, but I would like to use an inductive proof on the following type of structure. I have something of the form, for every $n \geq 2$ and for any $1 ...
6
votes
1answer
588 views

Principle of mathematical induction

In his book “Introduction to Mathematical Philosophy” Bertrand Russell seems to reach the conclusion that mathematical induction is a definition and not a principle. In essence he states that ...
6
votes
1answer
368 views

Nested Radicals Induction

How can I show that $\sqrt[2]{2+\sqrt[3]{3+\sqrt[4]{4+\cdots}}} $ (repeated $n$ times) is irrational using induction? I know the base case for $n=1$ looks like: $\sqrt[2]{2}$ is irrational. I also ...
6
votes
0answers
586 views

Examples of proofs by induction with respect to relations that are not strict total orders.

I have read this Wikipedia article and found it fascinating. I came across it after I tried to prove a certain statement with a method resembling induction in the set of natural numbers but ordered by ...
5
votes
2answers
69 views

Let $(F_n)_{n\in \mathbb{N}}$ be the Fibonacci sequence. Prove that $F_{n+1}F_n - F_{n-1}F_{n-2} = F_{2n-1}$.

Let $(F_n)_{n\in \mathbb{N}}$ be the Fibonacci sequence. Prove that $F_{n+1}F_n - F_{n-1}F_{n-2} = F_{2n-1}$. I'm trying to prove usinge the induction principle, so here is my sketch: $(i)$ $n = 3 \...
5
votes
1answer
100 views

Prove that $S_i<1$ for all $i$ by induction

We define $x_1=\frac12$, and $x_n=(1-\frac{3}{2n})\cdot x_{n-1}$ Then we define $S_i=x_1+x_2+\cdots+x_i$ Prove that $S_i<1$ for all $i$ I can see that $x_n=(1-\frac{3}{2n})\cdot (1-\frac{3}{2n-...
5
votes
1answer
82 views

Prove that the ant can survive

There is a table with infinite cells. An ant starts from cell $(1,1)$ and each time it can move one cell up or right. Before starting to move, an infinite sequence of cell numbers like $<(x_{1},y_{...
5
votes
0answers
196 views

Strange Algebra

I am working on a mathematical induction worksheet and my professor gave us the key and I have run across something that makes zero sense to me so please explain if you can. Additional info: $k \ge2$ ...
5
votes
0answers
423 views

Sum of like powers equal to a power

It's not hard to prove that $$(1+2+3+\ldots+n)^2=1^3+2^3+\ldots+n^3$$ ( for example using induction ) A generalization of this is also known : $$(\sum_{d \mid n} \tau(d))^2=\sum_{d \mid n} \tau(d)^3$...
5
votes
1answer
63 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 ideas?...
5
votes
0answers
180 views

${n \choose r}=\frac {n!}{r!(n-r)!}$ without using the permutation approach.

I had an idea that would be to first prove Pascal's Rule, $${n \choose r} = {n-1 \choose r-1} + {n-1 \choose r},$$ which can be proved combinatorically whether one particular element (among the $n$) ...
4
votes
0answers
50 views

Prove, by the process of Mathematical Induction, that: $\sqrt 1 + \sqrt 2 + … + \sqrt{n} < \frac{4n+3}{6}\sqrt{n}$ for all integers n > 0.

So what I am stuck on is proving the inequality for n=k+1. I have my teacher's solution, but it doesn't quite make sense to me. Teacher's solution: $\sqrt 1 + \sqrt 2 + ... + \sqrt{k} + \sqrt{k+1} &...
4
votes
0answers
142 views

Alternative proof of the generalized associative law for groups

The generalized associative law for groups claims that the value of $a_1\star a_2\star ... \star a_n$ is independent of how it is bracketed, where the symbols denote the usual notations of group ...
4
votes
0answers
88 views

For a simple graph of girth 5 and with minimum degree $k$ has at least $k^2+1$ vertices.

I know this problem can be done directly but I have tried this using Induction. I want your help in understanding where my proof is wrong. Proof: We will use induction on n (number of vertices of the ...
4
votes
0answers
89 views

Strong Induction Number Theory

I am having trouble using strong induction with the following problem: Show that for any fixed positive integer $n$, the sequence, $2,2^{2}, 2^{2^{2}}, 2^{2^{2^{2}}},...$ is eventually constant ...
4
votes
0answers
199 views

Proof by induction on an uncountable interval

I'm a little bit confused as to whether or not I can use proof by induction on an uncountable interval. For example, I'm trying to prove that $$(x+y)^n \leq x^n + y^n$$ on the interval $0 \leq n \leq ...
4
votes
0answers
221 views

Proof that all natural numbers (except 1) have a predecessor using Well-Ordering Principle

Context: This question arises from the unsuccessful search for a proof (that does not use induction) of a result used to prove the equivalency of the Well-Ordering Principle ("WO") and ...
4
votes
0answers
207 views

Another proof for Cayley-Hamilton theorem for modules by means of induction on the number of generators

Let $R$ be a unitary commutative ring, let $I$ be an ideal of $R$ and let $M$ be a finitely generated $R$-module. Suppose that $\phi$:$M$$\to$$M$ is a homomorphism such that $\phi$($M$)$\subseteq$$IM$....
4
votes
1answer
244 views

Review: Prove by induction Nicomachus's theorem

Please help me out reviewing the way I wrote this proof: Prove by induction: $1^3+2^3+3^3+...+n^3=\left(\frac{n(n+1)}{2}\right)^2$ with $n\geqslant1$ Proof: Lets define the set, $S=\left \{n\in N:n\...
4
votes
2answers
164 views

Induction and Trees

Let $d_1, d_2, \ldots, d_n$ be $n$ positive integers, with $n ≥ 2$. Prove: there exists a tree with vertex degrees $d_1, d_2, \ldots, d_n$ if and only if the sum $d_1 + d_2 + \cdots + d_n = 2n − 2$. ...
4
votes
0answers
64 views

$f(x)\in\mathbb{Q}[x]$ such that $f(\mathbb{Z})\subseteq \mathbb{Z}$ Then show that $f$ has the following form

Let $f(x)\in\mathbb{Q}[x]$ be a polynomial of degree $n$ such that $f(\mathbb{Z})\subseteq \mathbb{Z}$. I want to show that $f$ has the following form $$f(x)=\sum_{j=0}^{j=n} a_{j}\binom{x}{j}$$ ...
4
votes
0answers
77 views

Equality of Floors of some Partial Sums

Let $S_n=\frac{1}{1!}+\frac{1}{2!}+\cdots+\frac{1}{n!}$ denote the $n$th partial sum in the series expansion for $e=\sum\frac{1}{k!}$. I want to prove that $\lfloor n\cdot(S_n+1/n!)\rfloor=\lfloor n\...
4
votes
0answers
162 views

Empty Twin Prime Sets

Consider this set of numbers: $$1, 5, 8, 11, 13, 31, 37, 53, 61, 73, 79, 97, 122, 127$$ This is the set of numbers $n$ such that $nm \pm 1$ is not a twin prime pair for all $m \leq n$. For instance,...
4
votes
0answers
431 views

Proof by “continuous induction”

There’s a method of proving inequalities over some interval of real numbers using differentiation. For instance to prove that $x-\log(1+x) \geqslant 0$ whenever $x \geqslant 0$ we can differentiate ...
4
votes
0answers
179 views

Proof of inequality involving binomial coefficients

Proving things is not my forte. Stumbled upon following identity: $$\binom{n+k+1}{k}>\sum_{i=1}^k \binom{\alpha_i}{i}$$ For $\alpha_i<\alpha_j $ for $i<j$ $0\leq \alpha_i \leq n+k$ Also $...
4
votes
0answers
75 views

Induction proof - not sure how to proceed with next step

Define two sequences $A_n, B_n$ as follows: \begin{align*} A_1 &= 1\\ A_2 &= 3\\ A_3 &= 2 \cdot 3+1=7 \\ A_4 &= 2 \cdot 7 + 3 = 17\\ A_5 &= 2 \cdot 17 + 7 = 41\\ A_n &= 2A_{n-...
4
votes
0answers
570 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 $$(1)\...
4
votes
2answers
236 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 ...
4
votes
1answer
90 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. ...
4
votes
0answers
246 views

Induction on Primitive Recursive Function

The set $F_{n}$ of primitive recursive function symbols of arity $n$ can be defined inductively as: \begin{align} & Z, \text{Succ} \in F_{1} & \\ &\pi_{j}^{n} \in F_{n} \quad \text{for ...
4
votes
0answers
283 views

Efficiently count possible nim-like moves

Consider $n$ piles of coins, with pile $i$ having $a_i$ coins. A valid move is to remove zero or more coins from each of the piles, with the constraint that atleast one pile should remain unchanged, ...
4
votes
0answers
874 views

Induction in proof of multiplicativity of Euler totient function

(Updated below) I'm working through John Stillwell's Elements of Algebra, and while his exercises are generally crafted to be not too difficult, there's one that I don't even understand what it's ...
4
votes
0answers
151 views

Transfinite induction and valuation rank

In Engler's valued fields, exercise 3.5.2 goes as follows Construct valuations on $\Bbb{C}$ of rank $\kappa$ for every cardinal $\kappa \leq 2^{\aleph_0}$. The idea behind this (for any countably ...
4
votes
0answers
442 views

Group-theoretic proof that an increasing multiplicative function is exponential

Let $f:\mathbb{N}\rightarrow\mathbb{N}$ be a strictly increasing function such that $$f(2)=2$$ and $$f(mn)=f(m)f(n)$$ for all positive integers $m,n$ such that $$\gcd(m,n)=1$$ Prove that $f(n)=n$ ...
3
votes
1answer
95 views

What is the formal justification for finite induction?

Let $P(k)$ be a well formulated mathematical statement (in the FOL language of ZFC) involving $k\in \mathbb{N}$. Suppose I want to show that $P(k)$ holds for all $1\leq k \leq m$ for some fixed $m\...
3
votes
0answers
34 views

Maximum number of ones in triangular array of 0's and 1's

Assume that first row of the triangular array is $a_1, a_2,\dots,a_n$ which only contains 0's and 1's. We will build second row $b_1, b_2,\dots,b_{n-1}$ in this way : $b_i= a_i\operatorname{XOR} a_{...
3
votes
0answers
49 views

Prove that there is at least one excellent contestant

Consider a tournament in which each contestant plays every other contestant exactly once, and one of them wins. We’ll say that a contestant $x$ is excellent if, for every other contestant $y$, ...
3
votes
0answers
82 views

Show that $\sum_{k=1}^n k^{p}$ can always be written in the form $\frac{n^{p+1}}{p+1} + An^{p} + Bn^{p-1}+Cn^{p-2} + \cdots$

The following is a problem from my textbook: Using the telescoping method, show that $\sum\limits_{k=1}^n k^{p}$ can always be written in the form $\dfrac{n^{p+1}}{p+1} + An^{p} + Bn^{p-1}+Cn^{p-2} ...
3
votes
0answers
57 views

A combinatorial argument to prove a general inequality

Recently, I have seen the following argument: $$f(x) < Dx + f\left(\frac{x}{2} \right)$$ $$\Rightarrow f(x) < Dx + f \left( \frac{x}{2} \right ) < Dx + \frac{Dx}{2} + f \left(\frac{x}{4} \...
3
votes
0answers
105 views

Recursion-like sequences which are hard to relate recursively

Consider the sequence \begin{align*} a_1&=1\\ a_2&=2+\sqrt1\\ a_3&=3+\sqrt{2+\sqrt1}\\ &\kern5.5pt\vdots\\ a_n&=n+\sqrt{n-1+\sqrt{\cdots+\sqrt{1}}}. \end{align*} ...
3
votes
0answers
277 views

Simple Proof of Binomial Theorem for Negative Integer Powers

There's a vast amount of clutter on the internet about this which I've been trawling through but it does not answer exactly what I'm asking which, because superficially similar questions have been on ...
3
votes
0answers
99 views

Group of square free order with a normal $p$-Sylow is solvable

Let $G$ be a group of order $p_1...p_s$ where $p_1,...,p_s$ are distinct primes. If $G$ has a normal $p$-Sylow subgroup, then $G$ is solvable. We proceed by induction on $s$. If $s = 1$, $G$ is ...
3
votes
1answer
88 views

Show that if $2^k\in S\space\space\forall k\in\mathbb{N}$, and if $k\in S$ and $k\ge2$, then $k-1\in S$, then $S=\mathbb{N}$

Show that if $2^k\in S\space\space\forall k\in\mathbb{N}$, and if $k\in S$ and $k\ge2$, then $k-1\in S$, then $S=\mathbb{N}$ My attempt: Let $n\in\mathbb{N},$ hence $2^n\in\mathbb{N}$ by the first ...
3
votes
2answers
110 views

What is the $n$-time iterated adjugate of an $n\times n$ matrix $A$?

What is $\underbrace{\text{adj}\Big(\text{adj}\big(\ldots(\text{adj}}_{n\text{ adj}}\ A)\ldots\big)\Big)$, where $\text{adj}$ is written $n$ times, and the order of the matrix $A$ is $n\times n$? Can ...

1
2 3 4 5
20