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

what is wrong in my proof using simple induction?

I will prove $p(n):\ $Any $n$-cent postage where $n \ge 12$ can be made up using $3$-cents and $7$-cents stamps. My proof:(simple induction) Base case: as $12= 3+3+3+3$. So it can be made using $3$-cent. Inductive case: I am assuming that $n$…
SKL
  • 9
0
votes
3 answers

Prove that $\frac23 + \frac29 + \dots + \frac{2}{3^n} = 1 - \left( \frac13 \right) ^n$

Prove that: $$\frac23 + \frac29 + \dots + \frac{2}{3^n} = 1 - \left( \frac13 \right) ^n ,\text{for all } n > 0$$ I'm trying to do it using induction, thus: For the smallest possible $n$, we have $n = 1 \Rightarrow \frac23 = 1 - \left( \frac13…
Ziezi
  • 631
0
votes
3 answers

Prove using induction $\ln(n!)\leqslant n\ln(n)$ for $n\geqslant 1$.

Base case true $$\ln((n+1)!) = \ln(n+1)+\ln (n!)$$ Product rule But now I'm suck Idk how to prove that is less than or equal to $(n+1)\ln(n+1)$
mike lansing
  • 1
0
votes
1 answer

Induction proof - divisibility by 3

We want to show whether or not $2^{2n+1}+1$ Is divisible by 3 using induction. I tried doing this but I'm stuck with $2^{2n+3} + 1= 2^2 \cdot 2^{2n+1} + 1$. I don't know how to show if this is divisible by 3.
Johannes
  • 3
0
votes
4 answers

Trying to learn the basics of series of sums and proof by induction

I'm trying to get better at writing recursive algorithms and the book I'm studying with ("Thinking Recursively with Java") goes into a discussion of inductive proofs in Chapter 2. An introduction to inductive proofs provides as datum: $1 + 2 + 3 +…
Steven Harms
  • 1
0
votes
5 answers

How to prove if this $\sum_{l=0}^{n}\binom{n}{l}=2^{n}$ is valid for all $n\in \mathbb{N}$?

Prove for for all $n\in \mathbb{N}$: $\sum_{l=0}^{n}\binom{n}{l}=2^{n}$ I know the steps of induction but i have no idea how to prove this equation with binomial coefficient. 1) For the induction base i need to take one number and it should be…
Tars Nolan
  • 387
0
votes
5 answers

How do I prove that for $\forall n\in \mathbb{N}$ $\sum_{k=1}^{n}k(k+1)=\frac{1}{3}n(n+1)(n+2)$?

How do I prove that for $\forall n\in \mathbb{N}$ $\sum_{k=1}^{n}k(k+1)=\frac{1}{3}n(n+1)(n+2)$? I need to use induction. For example if n=1. Than 2=2. If statement holds for $\forall n\in \mathbb{N}$ then follows for $n +…
Alen
  • 531
0
votes
1 answer

Prove that $\sum_{i=1}^{n^2} \left \lfloor \sqrt{i} \right \rfloor = \frac{n(4n^2 - 3n + 5)}{6} $ using induction?

Clearly, it's true for n=1. Assuming true for n=k, we have $$\left \lfloor \sqrt{1} \right \rfloor + \left \lfloor \sqrt{2} \right \rfloor ..... + k = \frac{k(4k^2 - 3k + 5)}{6} $$ But how can we prove that $$\frac{k(4k^2 - 3k + 5)}{6} + \left…
Sharat
  • 349
0
votes
1 answer

proof of an equivalence

I am trying to prove something by induction, and in induction step I had to prove this $$1+ \sum_{k=1}^{\lceil{\frac{n-1}{2}}\rceil} (-1)^{k}\frac{(t^2)^{2k}}{(2k)!} = \sum_{k=0}^{\lfloor{\frac{n}{2}}\rfloor}(-1)^k \frac{(t^2)^{2k}}{(2k)!}. $$ Any…
J. Mccain
  • 65
0
votes
3 answers

Mathematical Induction proof $\sum_{k=0}^n 11^k$

I have a question about methematical induction. I have to proof that: $\require{cancel}$ $$\sum_{k=0}^n 11^k$$ Knowing that: $$\sum_{k=0}^n a^k = \frac{1 - a^{k+1}}{1-a} $$ I have the base: $$ 11^0 = \frac{1-11^{0+1}}{1-11}$$ $$ 1 =…
Fabiano Araujo
  • 219
0
votes
4 answers

Use mathematical induction to prove that $n^ 3 − n$ is divisible by 3 whenever n is a positive integer.

Solution: Let $P(n)$ be the proposition “$n^3−n$ is divisible by $3$ whenever $n$ is a positive integer”. Basis Step:The statement $P(1)$ is true because $1^3−1=0$ is divisible by $3$. This completes the basis step. Inductive Step:Assume that…
Surdz
  • 627
0
votes
2 answers

Mathematical Induction to show positive real number other than 1

By mathematical induction I need to show that $a$ is a positive real number other than $1$, then $$\sum^n_{j=1}{a^j}=(a)\frac{1-a^n}{1-a}$$ For each natural number $n$. We us ethe first principle of mathematical induction. For the base case that…
cryptomath
  • 385
0
votes
1 answer

Use Complete Induction of set theory to prove $\frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + ... + \frac{1}{\sqrt{n}} > \sqrt{n}$.

Proove by the Complete Induction for every $n\in \mathbb{N}, n \geq 1$ $$\frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + ... + \frac{1}{\sqrt{n}} > \sqrt{n}$$. I know only the basis - $\frac{1}{\sqrt{1}} \geq \sqrt{1}$. But, I dont…
NM2
  • 721
0
votes
1 answer

How can I prove this by mathematical induction

$n!>n^{n/2}$. For every positive integer greater than $2$
Sead Mejzini
  • 161
0
votes
1 answer

Non inductive proof for square of odd integers

Can we argue that the square of every odd integer is of the form $8k+1$ using non inductive proof?
Praneeth Reddy Araka
  • 9
1 2 3
…
99 100