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
1 answer

Proof by induction. Let $f(0)=1$ and $f(n+1)= (n+1)f(n)$. Prove $f(n)=n(n-1)(n-2)...(2)(1)$

It says Proof by Induction, Strong induction or Well-order but I don't know how can i start. I tried proving for $f(1)= f(0+1)= 1(f(0))=1\times 1$ but $1(1-1)=0$ then I don't know what can I do
Kevin Duran
  • 133
1
vote
1 answer

Exercise of induction with logarithm

How to prove by induction that for all $n\in\mathbb{N},\,\,\, n\geq 6$ $$\displaystyle{20+n\log_2 n\leq n^2}$$
Roiner Segura Cubero
  • 3,923
1
vote
2 answers

Whats an example of a predicate where if $P(1)$ is False, and $(\forall k\geq 1)(P(k)\implies P(k+1))$ is True for all natural numbers

The textbook solution just says that there is a predicate which satisfies those conditions. Wouldn't this be false since if the base case doesn't hold then by induction principle its false? Is there an example where $P(1)$ is False, and $(\forall…
user677216
  • 55
1
vote
0 answers

Strong induction

I have this question, Prove, $7 + 77 + 777 +7777 + 77...$n digits..$77 = 7/81[(10^n × 10) - 9n - 10]$ By induction. Now since this question was given in the exercise that involves proving various statements by strong induction, this one is to be…
user231094
  • 369
1
vote
3 answers

Prove by mathematical induction that $\sum_{i=0}^n (2i-1)^2 = \frac{n(2n+1)(2n-1)}{3}$

One of my homework problems is to prove that $\sum_{i=1}^n (2i-1)^2 = \frac{n(2n+1)(2n-1)}{3}$ I already completed the basis step $[2(1)-1]^2 = 1 $ $\frac{(1)[2(1)+1][2(1)-1]}{3} = 1$ Then I assumed that the proposition was true for n=k+1 which…
Mathdude388
  • 105
1
vote
1 answer

How to prove that for index i all the following n sums are positive?

Given are $n$ real numbers $x(1)$, $x(2)$, ..., $x(n)$. Some of them are positive, some may be negative. The total sum is positive. Prove the following statement: There exists some index $i$ such that all the following $n$ sums are…
user675160
1
vote
1 answer

Structural induction on expressions

Let $S$ be a recursively defined set of expressions. Base case, $v\in S$ Constructor Case: if $x\in S$ and $y\in S$, then $(x+y)\in S$ and $(x * y)\in S$ Prove by stuctural induction that for every $n \in S$, there exists $a,b\in\Bbb N$ such that…
user65065
  • 23
1
vote
2 answers

How to simplify this example from induction n(n+1)/2 + (n+1)

I am trying to figure out the steps here, not even sure what to really google as the topic to understand it. My thoughts are Multiply it out to get $\dfrac{n^2}{2} + \dfrac{n}{2} + (n + 1)$ You then times by $2$ to get ${n^2} + {3n} + {2}$ But…
perkss
  • 123
1
vote
2 answers

Prove $3^n > n2^n$ by induction

In proving $3^n > n2^n$ by induction for $n \geq 0$, I have so far got: $3^{n+1} = 3 \times 3^n > 3 (n2^n)$ In order to complete the proof, I have to show that $3n2^n > (n + 1) 2^{n+1}$. But this last inequality is only valid for $n > 2$, even…
1123581321
  • 954
1
vote
1 answer

Is explicitly stating "inductive hypothesis" necessary in proof by induction?

In one of my proofs, I wrote "Assume, {stating inductive hypothesis}" and in inductive step "We know that ... holds for k-1" instead of writing "Inductive hypothesis: {stating inductive hypothesis}" and "... holds for k-1 from inductive hypothesis".…
Yahya Rafiyev
  • 85
1
vote
1 answer

Show that $\sum_{k=1}^{n}(5^{2k}-5^{2k-1})=\frac{5^{2n+1}-5}{6}$, for n = 1,2,3, ...

Show that $\sum_{k=1}^{n}(5^{2k}-5^{2k-1})=\frac{5^{2n+1}-5}{6}$, for n = 1,2,3, ... n = 1 $LHS = 5^2 - 5 = 20$ $RHS =\frac{ 5^{3} - 5}{6} = \frac{120}{6} = 20$ n = p $LHS_{p} = (5^{2(1)}-5^{2(1)-1}) + (5^{2(2)}-5^{2(2)-1})+....+…
Daniel Andersson
  • 375
  • 2
  • 9
1
vote
2 answers

Show with induction that $\sum_{k=1}^{n} \frac{k^{2}}{2^{k}} = 6 - \frac{n^2+4n+6}{2^{n}}$

Show with induction that $\sum_{k=1}^{n} \frac{k^{2}}{2^{k}} = 6 - \frac{n^2+4n+6}{2^{n}}$ n = 1 $LHS = \frac{1}{2}$ $RHS = 6 - \frac{1+4+6}{2} = \frac{1}{2}$ n = p $LHS_{p} = \frac{1^{2}}{2^{1}} + \frac{2^{2}}{2^{2}} + \frac{3^{2}}{2^{3}} + ...…
Daniel Andersson
  • 375
  • 2
  • 9
1
vote
1 answer

Show with that induction $\sum_{k=0}^{n} 2{^{2k}}=\frac{2^{2n+2}-1}{3}$, for n = 0,1,2...

Show with that induction that $\sum_{k=0}^{n} 2{^{2k}}=\frac{2^{2n+2}-1}{3}$, for n = 0,1,2... My attempt n = 0 $LHS = n^0 = 1$ $RHS = (2^2 - 1 ) / 3 = 1$ n = p $LHS_{p} = 2^{2(0)}+2^{2(1)}+2^{2(2)}+...+2^{2(p)}$ $RHS_{p} =…
Daniel Andersson
  • 375
  • 2
  • 9
1
vote
3 answers

Prove with induction $\sum_{k=1}^n\frac{1}{(2k-1)(2k+1)(2k+3)}=\frac{n(n+2)}{3(2n+1)(2n+3)}$

Prove with induction the identity $\sum_{k=1}^n\frac{1}{(2k-1)(2k+1)(2k+3)}=\frac{n(n+2)}{3(2n+1)(2n+3)}$ How can I solve this problem? Should i set k= (p+1) and n = (p+1), then try to get the left side equal to the right side?
Daniel Andersson
  • 375
  • 2
  • 9
1
vote
4 answers

Show With Induction that $2\cdot2^{0}+3\cdot2^{1}+4\cdot2^{2}+...(n+1)\cdot2^{n-1}=n\cdot2^{n}$

Show with induction that $2\cdot2^{0}+3\cdot2^{1}+4\cdot2^{2}+5\cdot2^{3}+6\cdot2^{4}+...(n+1)\cdot2^{n-1}=n\cdot2^{n}$ My solution: Base case 1: n = 1 LHS = $(1+1)\cdot2^{1-1} = 2$ RHS = $1\cdot2^{1}= 2$ Case 2: n = p When $LHS_{P}$ =…
Daniel Andersson
  • 375
  • 2
  • 9
1 2 3
…
99 100