Mathematics Stack Exchange
Mathematics Stack Exchange

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.

Mathematical induction is a form of deductive reasoning. Its most common use is induction over well-ordered sets, such as natural numbers or ordinals. While induction can be expanded to class relations which are well-founded, this tag is aimed mostly at questions about induction over natural numbers.

In general use, induction means inference from the particular to the general. This is used in terms such as inductive reasoning, which involves making an inference about the unknown based on some known sample. Mathematical induction is not true induction in this sense, but is rather a form of proof.

Induction over the natural numbers generally proceeds with a base case and an inductive step:

  • First prove the statement for the base case, which is usually $n=0$ or $n=1$.
  • Next, assume that the statement is true for an input $n$, and prove that it is true for the input $n+1$.

The following variant goes without a base case: Assuming the statement is true for all $n\in\mathbb N$ with $n < N$, prove that is true for $N$, too. This has to be done for all $N\in\mathbb N$.

10150 questions
1
vote
3 answers

Infinite descent method and strong induction

I encountered the following statement of the infinite descent principle (PID): PID. Let $p(n)$, $n \in \mathrm{N}$, be an arbitrary property of natural number $n$. Assume that (e) $p(1)$ is a true statement and (f) for all $k \in \mathrm{N}$, if…
user782220
  • 3,195
1
vote
1 answer

scheme for n-dimensional induction

In slides: http://www.mathdb.org/notes_download/elementary/algebra/ae_A2.pdf I read the scheme for 2-dimensional induction, but Exists an scheme for n-dimensional induction? Thanks in advance!
mle
  • 2,287
1
vote
1 answer

How to proof (using by mathematical induction)($n\in \mathbb{N}$)

I would appreciate it if somebody could help me with the following problem: Q: How to proof (using by mathematical induction)($n=2,3,4,\cdots$) $$\left(1+\frac{1}{n}\right)^n<1+\frac{1}{1!}+\frac{1}{2!}+\cdots+ \frac{1}{n!}$$
Young
  • 5,492
1
vote
1 answer

Proof by induction and inequalities

I am stuck on this question: given $a_1a_2≤(\frac{a_1+a_2}{2})^2$ prove by induction of m that $$a_1a_2...a_p≤(\frac{a_1+a_2+...+a_p}{p})^p$$ where $a_i$ are all positive and real and $p=2^m$ (an increase in m unity doubles the number of factors in…
user135842
1
vote
2 answers

find the total Q

hello i have a problem with exercise the problem is follow: Consider the set $Q$ of integers defined as follows: $1 ∈ Q$ If $b ∈ Q$, then $2b-1 ∈ Q$ If $b ∈ Q$, then $2b +1 ∈ Q$ What is the total $Q$? Prove your answer carefully. I have found a…
Maria
  • 11
1
vote
1 answer

Prove by induction $n^{n+1}>(n+1)^{n}$, for $n\geq3$

I got some question on how to proceed on the proof below, Prove that: $n^{n+1}>(n+1)^{n}$, for $n\geq3$ By induction: Inequality holds for $n=3$ , $3^4=81\geq 4^3 =64$. Suppose it holds for $k^{k+1}>(k+1)^{k}$. Prove for $k+1$…
evaz34
  • 25
  • 2
1
vote
3 answers

Basic Induction Problem

For $N \geq 4$, prove $2^N \geq N^2$. I have the base case, $N=K$, and $N=K+1$ steps, but I am stuck at this point... $2^K\cdot 2 \geq (K+1)^2$ Thanks!
Teddy Six Strings
  • 13
1
vote
1 answer

Proof by induction, simplification step

i have to prove (3/4)(5^(k+2) -1) I have so far (after using inductive hypothesis etc): (3/4)(5^(K+1) -1) +3*5^(K+1) I can't seen to find a useful common factor to simplify although i'm sure it would be 3*5^(k+1) any help would be appreciated! Also,…
pablo
  • 25
1
vote
1 answer

Proof for positive integer

Prove that for any positive integers $m$ and $n$, there exists a set of $n$ consecutive positive integers each of which is divisible by a number of the form $d^m$ where $d$ is some integer in $\mathbb{N}$.
Apoorv Jain
  • 720
1
vote
2 answers

$2+4+6+\cdots+2n=n^2+n$ by mathematical induction

I am trying to prove $2+4+6+\cdots +2n=n^2+n$ by mathematical induction. I followed all the steps and the $P_{k+1}$ was $2+4+6+\cdots+2(k+1)=(k+1)^2+k+1$ Starting from the left hand side of the equation I have solved till $k^2+k+2(k+1)$. Now I am…
user2857
1
vote
1 answer

Inductive step assumption for all numbers up to $n$

I know that the inductive step should be "for all $n$ (if $P(n)$ then $P(n+1)$)" and NOT "if (for all $n$ $(P(n)$)) then (for all $n$ ($P(n+1)$))" - see this answer. But can it be like "if (for all $i$, where $i = 1, \ldots, n$, ($P(i)$)) then…
betatester07
  • 151
1
vote
1 answer

Induction proof $2^{n+1}-1$ when n is 50

There are 50 of YES or NO questions. Supposed store them into a binary tree. Each path from root to leaf implies a possible answer to the questions. The number of vertices for $n$ question is $2^{n+1}-1$ How to prove $2^{51}-1$ vertices in the…
Evan S
  • 75
  • 1
  • 1
  • 6
1
vote
3 answers

Induction proof $a_n$ is even for n $\ge$ 1

$$a_1=0, a_2=2, a_3=2, ... a_k = a_{k-2}+3a_{k-3}$$ for k $\ge$ 4 Initial case n = 1 given above it is true as zero is divisible by 2. Let n = k. Assume that $a_{k+1} = a_{k-2+1}+3a_{k-3+1} $ That is $a_{k+1} = a_{k-1}+3a_{k-2} $ How to prove by…
Evan S
  • 75
  • 1
  • 1
  • 6
1
vote
0 answers

greatest common divisor via induction?

could someone provide a nice explaination for the following problem. I´m repeating some old exercises and stuck with this one: I have to prove via induction from $(n-1)$ to $n$ for all natural $n,m$ $\in$ $\mathbb{N_+}$ that relationship: (greatest…
Jacky
  • 87
1
vote
0 answers

Taylor's Approximation proof by induction

I'm really stuck on this question Let $f(x)$ be a function on $[a,b]$ which is $(n + 1)$ times differentiable at every point, for some natural number $n$. Let $c$ be a point in $(a,b)$. Using induction and the generalized mean-value theorem prove…
Maths_hurts_me
  • 11
1 2 3
…
99 100