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
0
votes
3 answers

Induction: Proving 2 Simple Weak Inequalities with Exponents of 2 and 3

I was wondering if you could help me with a trivial problem with inequalities that my teacher didn't really explain. Take for example: $3^n+2 ≤ 3^{n+1}$. How can I formally prove something as trivial as that inequality. (For $n \in…
OFRBG
  • 1,096
0
votes
3 answers

Stuck on trying to even start proving $2\mid (n^4-3)$ if and only if $4\mid (n^2 + 3)$

How would you prove $2\mid (n^4-3)\iff 4\mid (n^2 + 3)$. Can you use induction on both at same time? Can I just do it directly somehow?
andemw01
  • 207
  • 1
  • 5
0
votes
1 answer

prove that $\left\lvert \sum_{i=1}^{n} a_i \right\lvert \ ≤ \ \sum_{i=1}^n \lvert a_i \lvert$

Please comment on my proof, see if I made some mistakes. For $n \in \mathbb{N^+}$, $a_i \in \mathbb{R} (1 ≤ i ≤ n)$, prove that $$\left\lvert \sum_{i=1}^{n} a_i \right\lvert \ ≤ \ \sum_{i=1}^n \lvert a_i \lvert$$ Denote the above proposition as…
DSL
  • 1,359
0
votes
6 answers

Proving $1+3+\cdots+(2n-1) = n^2$ using induction

$ 1+3+\cdots+(2n-1) = n^2$ Base case; $n=1$, holds true since $1=1$ Induction Hypothesis; Suppose $ 1+3+\cdots+(2k-1) = k^2$ Then; I have trouble with $2k+1$ do i add $2k+1$ to both sides or multiply them?
TheGamer
  • 393
0
votes
0 answers

How to prove Corollary Let $k \in \mathbb{Z}$, and $P(x)$ be a formula in one variable such that (1) $P(k)$ and (2) $(\forall x ≥k)P(x)\implies P(x+1$

Prove Corollary Let $k \in \mathbb{Z}$, and $P(x)$ be a formula in one variable such that (1) $P(k)$ (2) $(\forall x ≥k)P(x)\implies P(x+1)$ Then $$\forall \in \mathbb{Z}x≥k \implies P(x)$$ Question This can be proved by defining a new formula…
DSL
  • 1,359
0
votes
3 answers

mathematical induction in actual number

Mathematical induction in natural number is proved with axiom of natural number. I'm curious about is it possible to extent mathematical induction into real number range. Can the mathematical induction be established in axiom of actual number? Or is…
ABC
  • 73
0
votes
2 answers

State the well-ordering principle as an if-then statement with an inequality using as many symbols as possible

I can't find a statement of the well-ordering principle that is an if-then statement that uses as much mathematical symbolic notation as possible. I want the if-then statement to involve an inequality, subset notation, invoke the natural numbers,…
user420360
0
votes
1 answer

mathematical induction explanation in: elementary number theory by David M. Burton

I don't see a clear difference between $(ii)$ and $(ii')$, is $(ii')$ referring to k being a specific integer along the positive integer line whereas $(ii)$ is referring to any integer of k? (sorry if i'm missing something obvious)
Sonny Da Silva-Peters
  • 316
0
votes
1 answer

Advanced Induction proof

I have to prove the following inequation by induction $$\sum_{k=2^{n+1}}^{2^{n+2}-1} a_k \leq 2^{n+1} \cdot a_{2^{n+1}}$$ but I have trouble with the inductive step when I have to choose $k = 2^{n+2}$. We also know that $ a_1 \geq a_2 \geq a_3 \geq…
Razmo
  • 47
0
votes
2 answers

Regarding proof by Induction

If I constructed a proof that worked like this, shown true for n=1. If assumed true for n=k then shown to be true for k-1 (i.e. rather than k+1) blah blah .. Is this just no proof at all or has it got any validity? Brian
nerak99
  • 183
0
votes
0 answers

Prove by induction of binomial coefficients

Prove using induction that the binomial coefficient $\binom nr$ is always a natural number for all $n$ and for $0≤ r ≤ n$ I tried proving it but i failed .what should i do?
Abdullah Alfaqir
  • 183
0
votes
1 answer

Simple Proof by Induction

I am asked to prove by induction that $4 + 9 + 14 + ... + 5n - 1 = \frac{n}{2}(3 + 5 n)$ As I understand it, during the induction step, one should replace $k$ by $k + 1$. However, in the solution, the induction step is as follows Let $n = k$ $4 + 9…
Pete
  • 13
0
votes
2 answers

Proof by mathematical induction: stuck on algebra

Use mathematical induction to prove the following: For all $i$ starting from $1$ up to $N$, $i^3 =\frac{N^2(N + 1)^2}{4}$ Base Case: $1 ^ 3 = 1^2(1 + 1)^2 / 4$ Conditions holds, so move onto general case. Assume true for $N = k$ $1 ^ 3 + 2 ^ 3 + 3 ^…
Perplexityy
  • 117
0
votes
1 answer

Induction proof on $\sum_{i=0}^n m^i=\frac{m^{n+1}-1}{m-1}$

For natural numbers $m\geq2$ and $n\geq1$, prove with induction that $\sum\limits_{i=0}^n m^i=\frac{m^{n+1}-1}{m-1}$. My first intuition is to prove that $n+1,m$ is true, then $n,m+1$, then possibly $n+1,m+1$, though I'm uncertain whether the last…
user154989
  • 195
0
votes
0 answers

Working with recurrence

$$ \DeclareMathOperator{ceil}{ceil} T(n) = \begin{cases} 10 & \text{ if } n=1 \\ 7 \, T(\ceil(n/2)) + n^2 & \text{ if } n>1 \end{cases} $$ a) Use n to find positive real constants c,d such that T(n) <= c n^{lg base 2 7} - d n^2, for all n…
user400098
1 2 3
…
99 100