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

Help with the algebra in for this number theory proof?

For all $n\geq 1$, prove with mathematical induction $\frac{1}{1^2}+\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{n^2}\leq 2-\frac{1}{n}$ So far.. I have substituted 1 and saw that the statement is true and I have plugged in n+1 to show that the…
Lil
  • 2,529
2
votes
1 answer

What is mutual induction and how does that differ from regular induction?

http://web.cecs.pdx.edu/~black/CS311/proof_by_mutual_induction.pdf I read this and I fail to see any difference. It's the same thing, prove for n = 0 and then prove for n = k+1.
user539484
  • 235
2
votes
4 answers

Proof that $x^k < k^x$

So, I want to prove that $x^k$ is less than $k^x$ for any $x > k$. $x$ and $k$ are both integers. My first approach was an induction over $k$, given that the numbers are integers. I also considered the facts that given a certain $k$, $x^k$ grows…
Setzer22
  • 237
2
votes
2 answers

Prove by induction that $P_{n}<2^{2^{n}}$, being $P_{n}$ the $n^{th}$ prime number

Prove by induction that $P_{n}<2^{2^n}$, been $P_n$ the $n^\text{th}$ prime number The prime numbers´s set is defined as $\mathbb P:= \left \{2,3,5,7,11,\ldots\right\} $ Let $P(n)$ be the proposition we want to prov, ie: $P(n):=P_n<2^{2^n}$ For…
Victor F Salazar G
  • 1,297
2
votes
1 answer

Prove by induction that $a_{1}+a_{2}+...+a_{n}=\dfrac{(a_{1}+a_{n})n}{2}, \forall n\in \mathbb N$

Prove by induction that $$a_{1}+a_{2}+...+a_{n}=\dfrac{(a_{1}+a_{n})n}{2}, \forall n\in \mathbb N$$ HINT: Supose that: $a_{i+1}-a_{i}= r, \forall i\in \mathbb N$ Let $P(n)$ be the proposition we want to prov, ie:…
Victor F Salazar G
  • 1,297
2
votes
1 answer

How to prove $(n!)^4\le2^{n^2+n}$?

This may sound like a newbie but question is to show that $$(n!)^4\le2^{n^2+n} for \quad n=1,2,3...$$ I know it is true for n=1. $(1!)^4\le2^2$ and assume it is true for $1
lyme
  • 1,351
  • 1
  • 13
  • 30
2
votes
4 answers

Prove by induction the following

In the decimal form of the number $3^n$, the second from the end digit is even. My proof so far: Base Case: $n=3$ $3^3=27$. The second from the end digit is even, so the base case is true. Inductive Step: Assume $n=k$ is true and prove $n=k+1$ is…
Mr Croutini
  • 1,158
2
votes
2 answers

Mathematical Induction help

Ok, so I'm not very good with these proving by induction thingies. Need a little help please. How do I prove $$\sum_{j=0}^n\left(-\frac12\right)^j=\frac{2^{n+1}+(-1)^n}{3\cdot2^n}$$ when $n$ is a non-negative integer. I got the basis step and such…
Rich Sanchez
  • 69
2
votes
2 answers

Mathematics induction (exponential divisible by 2304)

$7^{2n} -48n - 1$ is divisible by 2304 for all $n \in N$ so I did, P(n) : $7^{2n}-48n-1=2304k$ (k meaning there is an integer which will depend on n) Prove base case $P(1): 7^2 - 48(1)-1 = 0$, proving that $k=0$ in the meaning of 'divides'…
Joseph
  • 23
2
votes
1 answer

Naive question about ordinary vs. transfinite induction

I searched related topics but did not find any clear elucidation of this distinction. Ordinary induction can only be used to show that a property holds for every finite object, say every natural number. However, in order to show that a property…
Motorhead
  • 281
2
votes
2 answers

Show that $x|y \Rightarrow x \leq y$

I have to show that $x|y \Rightarrow x \leq y$ where $x,y \in \mathbb{N} \land x,y \neq 0$ Can someone give me a start hint how I can show this? I guess I can proof by induction. Not quite sure where to start $x|y \Leftrightarrow xn =y$
Chris
  • 521
2
votes
3 answers

When proving a statement by induction, how do we know which case is the valid 'base'?

For example proving 2^n < n!, 4 is the 'base' that works for this exercise, then starting from there we prove p + 1 considering p has to be at least 4 and we have our result. However, I believe determining the first valid value without a previous…
JOX
  • 1,509
2
votes
3 answers

Yet another confusion about Strong vs Weak Mathematical Induction - Wrong Proof?

In Mathematics literature, I am under the impression that there are at least two (non-trivially different) definition of Mathematical induction. I am assuming one is a weak form and the other is strong. Def 1 (weak form) (I believe that I have…
Dilawar
  • 6,125
2
votes
1 answer

Induction proof strategy - backward induction

Normally, when using induction, I assume a statement is true for n, then I will try to show the same statement is also true for n+1. In the problem I have now, is is correct if I assume a statement is true for n+1, then show that the statement is…
Peter
  • 1,955
1 2 3
…
99 100