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
2 answers

Mathematical Induction question

This question should be done using either strong induction or weak induction. If $111$ is a multiple of $3$ $111 111 111$ is a multiple of $9$ $111 1111111111111111111111$(to $n$) is a multiple of $3^n$ Prove this using induction
andrew
  • 143
0
votes
0 answers

How to prove a statement by mathematical induction?

Let $f: \mathbb{R} \rightarrow \mathbb{R}$ be a function satisfying $f(x+y) = f(x) + f(y)$ for any $x, y$ in $\mathbb{R}$. Suppose $f(x)$ is continuous at 0, and $f(1)$ equals a constant $a$. Show that $f(x) = ax$ The hint provided for this question…
statstudent
  • 25
  • 3
0
votes
1 answer

simple induction related question where we are doing it for k ∈ R

suppose we want to prove by induction that $$1^2+ 2^2+ 3^2+ 4^2+ ....... + n^2= \frac{n}{6}(n+1)(2n+1)$$ it is very easy where we assume $k$ and $k+1$. suppose we want to prove $$3^k>2^k, \forall k\in\mathbb R^+$$ then while doing induction (if…
Dusty_Wanderer
  • 282
0
votes
1 answer

Induction proving

I have this problem I need to prove: Prove that for every $n\ge3$ this statement is true: $2^n\ge2n+1$ I proved this by induction and it was easy for me. my question is about the second section of the question. Two sequences is given: $8, 16,…
BeardGuy367
  • 93
0
votes
2 answers

Proving $\left[1+\frac{1}{(n+1)^2}\right]^{(n+1)^2}-\left[1+\frac{1}{n^2}\right]^{n^2}>0$ for $n\geq 2$, by induction

I have to prove that $$\left[1+\frac{1}{(n+1)^2}\right]^{(n+1)^2}-\left[1+\frac{1}{n^2}\right]^{n^2}>0$$ for $n\geq 2$. I checked the base case and it holds true for $n=2$. Assume it is true for $n$…
Natasha J
  • 825
0
votes
0 answers

What are the cases for strong mathematical induction in which the proof of the implication in the inductive step doesn't work?

In Susanna S. Epp's book Discrete mathematics with applications, she writes,"However, in many cases the proof of the implication for k>b does not work for a≤k≤b. So it is a good idea to get into the habit of thinking separately about the cases where…
Zero dono
  • 1
0
votes
3 answers

How to prove this by mathematical induction?

ok! so i don't have a clue as to how to prove it. $$\sum\limits_{i=m+1}^n i=((n-m)(n+m+1))/2$$ so the base case is equal to zero because $$\sum\limits_{i=1+1}^1 i=0$$ is this correct? I don't know how to go for inductive step. Thanks in advance
Natasha J
  • 825
0
votes
0 answers

Use induction to prove the inequilities

Use mathematical induction to prove: $$\frac{n}{2} < \sum_{k=1}^{2^n-1}\frac{1}{k} < n$$ To prove the left part. Assume: $$\frac{m}{2} < \sum_{k=1}^{2^m-1}\frac{1}{k}$$ Want to prove: $$\frac{m+1}{2} < \sum_{k=1}^{2^{(m+1)}-1}\frac{1}{k}$$ I…
SixTwelfthsPi
  • 25
0
votes
2 answers

Induction Proof $4^k < 5^k$

So I need to use induction to prove that $4^n<5^n$ for all natural numbers $n > 0$. I have proved the base case to be true. For the induction hypothesis, we assume that when $n=k$, then $4^k < 5^k$. However, I am stuck in the inductive step when I…
tom786
  • 59
0
votes
2 answers

proof of $x\cdot y = \lfloor x/2\rfloor \cdot 2y + y$ if $x$ is odd.

I was reading this awesome book called "Algorithms" by "Jeff Erickson" and I came across this peasant multiplication he said it works because How can I prove the second statement by induction and what's the intuition behind it? EDIT: I understand…
Ahmed I. Elsayed
  • 217
0
votes
1 answer

Induction Problem Help, writing equation

There are $n$ piles of marbles and that every pile has a different number of marbles. We want to prove that the sum of the number of marbles in all the piles is greater than or equal to $\frac{n(n + 1)}{2}$, without knowing anything beyond the fact…
Lauren Zio
  • 31
0
votes
3 answers

Proof by Induction: $f^{n}(x) = 2^n n!(5-2x)^{-(n+1)}$

I have trouble understanding the following problem: "Consider the function $f(x)=(5-2x)^{-1}$: Proof by induction, for all $n \in \mathbb{N}_0$: $$f^{(n)}(x) = 2^n n!(5-2x)^{-(n+1)}$$ Additionally calclulate the taylorseries of $f$ for $x_0 =…
user13764911
  • 5
  • 3
0
votes
1 answer

Proof by induction: inequalities

I need to prove by induction the following inequality: $$\sum_{i=1}^{n} i \leq n^n \text{ for all } n \geq 1$$ Base case is proved. In the inductive case I can sum both sides of the inequality by $(n+1)$ as $$\sum_{i=1}^{n+1} i = \sum_{i=1}^{n} i +…
Cindy
  • 35
0
votes
1 answer

Proof by induction on coin problem

Suppose I have an unlimited supply of $k$th and $(k+1)$th cents where $k \in \mathbb{N}$, then I can always pay integer bills starting from $k(k-1)$ cents using only the two types of coins I have. Let this statement be $P(k)$. So, $P(1):$ I have…
Terrarium
  • 145
  • 5
0
votes
3 answers

Proof of divisibility of 3 sequential cubic numbers by induction

The task is to prove that the sum of three subsequent cubic numbers is divisible by 9. My approach looks like this: $n^3+(n+1)^3+(n+2)^3 = 9M$ Proof that the equation is true for $n=1$ $1^3+2^3+3^3 = 1+8+27 = 36;$ $ 36/9 = 4$ Assume that the…
Hohlkopf
  • 59
1 2 3
…
99 100