Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

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 ...

-3
votes
0answers
26 views

I need help proving this by the induction method [on hold]

So this is the problem: $$(a+b)^{n}=\sum_{k=0}^{n}\binom{n}{k}a^{k}b^{n-k}$$
0
votes
2answers
47 views

Struggling with what proof to use?

So this is a problem from my text book: A transaction string is a string over the alphabet $\{0,1,2,3,4,5,6,7,8,9,+,-\}$ in which: the operations $+$, $-$ never occur consecutively, and the last ...
0
votes
2answers
40 views

Proof of induction from higher starting point

I'd like to request to verify this proof that for a arbitrary natural $n_0$ this holds: $[C(n_0+1) $ and $\forall n>n_0 : C (n) \implies C (n+1)] \implies \forall n> n_0 : C (n) $ ($C (n)$ means ...
0
votes
0answers
17 views

Induction based on combinations and binomial theorem

I was looking at some questions in a Cambridge text and I reached this question however I am at it for 1 hr and can't seem to get the proof right. Any help ?
0
votes
3answers
47 views

How could I prove this? [duplicate]

$\newcommand{\intd}{\,\mathrm{d}}$On an AOPS forum a user solved that $$\int\frac{1}{x(x+1)(x+2)\ldots(x+n)}\intd{x}=\frac1{n!}\sum_{k=0}^n(-1)^k\binom{n}{k}\ln|x+k|+C$$ This to me is absolutely ...
0
votes
1answer
24 views

Proving the stability of fixed point

How do I prove the following statement : $$ \forall k \geqslant 1, \ |f^k(x)-p| \leqslant a^k|x-p|$$ inductively? $p$ is a stable fixed point of $f$ and $f'(p) \leqslant a < 1$. $f$ is a ...
2
votes
1answer
60 views

Proof by induction that you can order natural numbers where the average isn't between any pair of numbers

Consider a list of natural numbers like $$1, 2, 3, \dots, n$$ Prove using strong induction that you can order the list for any Natural n, in a way where if you pick any pair of numbers, the average ...
1
vote
1answer
60 views

Proof by induction for $f^{n+1}(x)=\frac{x}{\sqrt{1+(n+1)x^2}}$

Look at the following function f: $\mathbb{R} \to \mathbb{R}: x \mapsto \frac{x}{\sqrt{1+x^2}}.$ Show with the complete induction that the recursive ( given by $f^1:=f$ and $f^{n+1}:=f\circ f^n$) ...
0
votes
3answers
47 views

Prove by induction $\sum_{k=1}^n k^3 =( \sum_{k=1}^n k )^2 $

Can anyone show me how to prove this example by induction? I can't figure it out. $$\sum_{k=1}^n k^3 =\left( \sum_{k=1}^n k \right)^2 $$
0
votes
2answers
44 views

Prove by induction that $n^3 = (n^2-n+1)+(n^2-n+3)+…+(n^2+n-3)+(n^2+n-1)$

I have an exercise that asks me to prove that $n^3 = (n^2-n+1)+(n^2-n+3)+...+(n^2+n-3)+(n^2+n-1)$ by induction, but I got stuck: I don't know what I can do. Could you please give me some hints? ...
0
votes
1answer
41 views

Proof by induction: Let $a_0=3$ and $a_{n+1}=\sqrt{a_n+7}$ if $n>0$, Prove: $3<a_n<4$

Let $a_0=3$ and $a_{n+1}=\sqrt{a_n+7}$ if $n>0$ Prove: $3<a_n<4$ At first I was quite surprised it's actually true for the base cases: $n=0$, $a_1=\sqrt{3+7}=\sqrt{10}$ $n=1$, $a_2=...
3
votes
2answers
73 views

Prove that every natural number $n>15$ there exist natural numbers $x,y\geqslant1$ which solve the equation.

Prove that every natural number $n>15$ exist Natural numbers $x,y\geqslant1$ which solve the equation $3x+5y=n$. so i try induction. base case is for $n=16$. so $\gcd(5,3)=1$, after Euclidean ...
0
votes
2answers
18 views

Alternating series test [Question of monotone decreasing sequence]

I have to show that Let $n\in\mathbb{N}\cup\{0\}$ and let $(a_n)_{n}$ be defined as $a_n=(-1)^n\frac{n}{n^2+1}$. Check convergence of the series $\sum_{n=0}^{\infty} a_n$. Using the alternating ...
3
votes
5answers
58 views

Induction proof: Let $a_0=1,$ $a_{n+1}=10a_n-3$, Find an explicit formula for $a_n$

Let $a_0=1,$ $a_{n+1}=10a_n-3$ Find an explicit formula for $a_n$ I took this from a book called "A Walk Through Combinatorics" that I found online to practise combinatorics and induction proofs....
3
votes
2answers
91 views

Logic - Member of an inductive set that is not a member of the set of theorems in a formal system?

First question on this site. Hope to ask/answer many more in the future. I'm currently self-studying An Introduction to Mathematical Logic by Richard E. Hodel and came across an interesting exercise. ...
0
votes
3answers
59 views

Mathematical Induction and Recursion [closed]

Consider the following two-player game: starting with the single number 123, two players alternately subtract numbers from the set {1; 2; 3} from this value. The player who first gets this sum to 0 ...
-1
votes
1answer
48 views

Is my proof using induction complete?

I need to prove a statement involving two variables over non-negative integers. That is $P(a, b)$ for all $a\in \mathbb{Z_{\ge 0}}$ and $b \in \mathbb{Z_{\ge 0}}$ I did the following steps 1.$ P(a, ...
0
votes
1answer
39 views

Inequality proof with sequences

So I was doing part 2 of this question and I wanted to know if my approach is correct. $x_{n+1} - x_n = x_n^2 + 1/4 - x_n$ Now since it is a sequence of positive terms $x_n$ > 0 Therefore $x_n^2 +...
4
votes
2answers
120 views

Number theory, possibly mathematical induction to use

For $n, r \in \mathbb{N}$ denote $S_r(n)$ sum $1^r + 2^r + ... + n^r$. Verify that for all $n, r$ : $$(n+1)^{r+1} -(n+1) = \binom{r+1}{1}S_r(n) + \binom{r+1}{2}S_{r-1}(n)+ \cdots +\binom{r+1}{r}S_1(n) ...
0
votes
1answer
19 views

How do you determine how many cases to consider in base case of strong induction?

I'm trying to learn to strong induction and I'm beginning understand the steps. However I can't seem to understand why some examples have multiple base cases. What do you look for while choosing base ...
2
votes
4answers
96 views

How to prove AM-GM by induction 3

Let $a_1;a_2;...;a_n\ge 0$. Prove that $$\frac{\sum ^n_{k=1}a_k}{n}\ge \sqrt[n]{\prod ^n_{k=1}a_k}$$ We will prove it's true with $n=k$. Indeed we need to prove it's true with $n=k+1$ WLOG $a_1\le ...
1
vote
3answers
45 views

Prove by induction that $n^2 + n + 1 \forall n\geq 1$ given the following recurrence relation [closed]

My question is as follows: Consider the following recurrence relation: $a_{n} = a_{n-1}+2n$, with $a_{1}=3$ Prove by induction that $a_{n}=n^{2}+n+1 \forall n\geq 1$ I have no idea how to even ...
0
votes
2answers
37 views

Can anybody explain me the logic of the inductive step of strong induction?

To understand the strong induction, I read that it is kinda "equivalent" version of weak induction. So I learnt it from google, solved some examples. And it seems to be quite intuitive to understand. ...
2
votes
1answer
33 views

By induction prove $ P(n) := $ “$ B \rightarrow \varphi_{n}(B,\rightarrow)$”

Define $\varphi_{n}(B,\rightarrow)$ to be the statement form comprised of only the particular statement $B$ and connectives $\rightarrow$ such that $B$ occurs exactly $n$ times. So I'm actually ...
1
vote
1answer
33 views

How to know the statement on natural numbers is univariate or bivariate for induction

In order to prove the following recurrence $$\binom{n}{r} = \binom{n-1}{r} + \binom{n-1}{r-1}$$ It is enough to prove induction on only $n$, not needed to do induction on $r$. That is $P(0,0)$ $P(n,...
1
vote
1answer
43 views

Mathematical induction on binomial coefficients

I need to prove the following statement (Pascals Identity) on binomial coefficients using mathematical induction only $$\binom{n}{r} = \binom{n-1}{r}+\binom{n-1}{r-1}$$ My doubt is Whether I need ...
1
vote
3answers
54 views

In the principle of Mathematical Induction, why do we take the base case as $P(1)$ only? [duplicate]

I kinda understand the logic and motivation behind the proof, but what bothers me is the fact, why is the base case (the first statement that we write) is always $P(1)$ when we are proving a ...
2
votes
2answers
43 views

Have I used induction correctly in this proof of $x<y \implies x^n<y^n$?

A while ago I posted an attempt at a proof of $x<y \iff x^n<y^n$. It was pointed out that I hadn't actually used induction, and had instead done a direct proof. Below is the link to the question,...
1
vote
2answers
26 views

How are the properties satisfied in this induction proof?

I have some notes on the topic of the Principle of Induction (POI) from the perspective of the Well-Ordering Principle (WOP). The following claim has just been proved: Claim: (Principle of Induction) ...
1
vote
1answer
16 views

Identity for Euler-Darboux-Poisson (Evans 2.4 lemma 2)

The following identity is used in the treatment of the multivariate wave equation (Evans on p. 74) Lemma 2 (Some useful identities). Let $\phi:\Bbb R\rightarrow \Bbb R$ be $C^{k+1}$. Then for $k=1,...
1
vote
1answer
54 views

A question on Goldrei Theorem 3.13 : prove that if $n>m$ and $a>0$ then $a\cdot n>a\cdot m$

This question is about the proof of Theorem 3.13 b) in Goldreis' "Classic Set Theory": For all natural numbers $n,m,a$, if $a>0$ and $n>m$ then $a\cdot n>a\cdot m \quad(1.)$ It has ...
4
votes
2answers
85 views

Show that:$\sum_{i=1}^n x_{i} \cdot \sum_{i=1}^n \frac{1}{x_{i}} \geq n^2 $ [duplicate]

Show that:$$\sum_{i=1}^n x_{i} \cdot \sum_{i=1}^n \frac{1}{x_{i}} \geq n^2 $$ The following hints are also given: $$\left(\frac{x}{y} + \frac{y}{x} \geq 2 \right) \land x,y \gt 0$$ Base Case: For n = ...
0
votes
4answers
103 views

Prove by mathematical induction that $n^4 − n^3 + n^2 − n$ is divisible by $2$ for all positive integers $n$.

So I've done the base case with $n = 1$ and the general case of $k^4 − k^3 + k^2 − k = 2m$ but I can't seem to find a way to manipulate $(k+1)^4 − (k+1)^3 + (k+1)^2 − (k+1)$ in a manner such that I ...
2
votes
2answers
33 views

Proof using mathematical Induction

Suppose I am proving the statement $P(m,n)$ in natural numbers. Steps: 1) Proving $P(1,1)$ true 2) $P(m,n) \implies P(m+1,n)$ My doubt while proving second step is that, can I assume $P(m,1), P(m,...
5
votes
1answer
140 views

Understanding and proving prop 2.1.16 in Tao's Analysis I concerning recursive definitions

Notes: Tao's axioms and original proposition statement and proof are given below. Similar questions have been asked here and here, but I was not able to resolve my issues. In particular, I have ...
3
votes
8answers
127 views

Show that $x^2+9x+20$ is divisible by 2 for all $x \in \mathbb{Z}$

I'm having extremely hard time getting how proof by induction should work for this case. This is my attempt so far: (1) When $x = 1$ $1^2 + 9 + 20 = 30$ which is divisible by 2. (2) Now assume ...
3
votes
1answer
44 views

In a line of ones and zeroes, $10$ changes to $01$ every second. Prove that it takes no longer than $10n$ seconds until there are no more $10$s.

There is a line of ones and zeroes of length $n$. Every second, $10$ changes to $01$. Prove that it takes no longer than $10n$ seconds until there is nothing to change in the line. Example: ...
4
votes
2answers
98 views

Induction differential proof

So I was doing an induction proof that contained a differential. Now I got through most of it but lastly in order to complete the proof I needed to prove $$\frac{d^k }{dx^k}x^k=k!$$ Now I don't ...
0
votes
0answers
23 views

Does every iterative definition (or at least the one describe in the details) require the use of the Axiom of Choice? [duplicate]

One of my books gives the following proof that if the image of a sequence of real numbers $x_n$ has an accumulation point $x_0$, then there exists a subsequence $x_{n_k}$ convergent to $x_0$. The ...
3
votes
2answers
29 views

Is nested induction necessary for all variables

Let $S(n_1,n_2,n_3)$ be the statement to prove in natural numbers; If I prove the following three $S(1,1,1)$ is true $\forall n_1n_2 S(n_1,n_2,n_3) \implies S(n_1,n_2,n_3+1)$ $\forall n_1n_3 S(n_1,...
2
votes
1answer
33 views

Proof by induction on $r$ variables

If there is a statement $P(n)$, proof by induction has three steps. Base case is to show $P(1)$ is true Induction step is to assume $P(K)$ is true and then to show $P(k+1)$ is true. If our ...
0
votes
2answers
40 views

Induction proof inequality

So I got this induction proof question but I can't seem to make a logical statement in one part of it: The question is , $a_{n + 1} = 5 - \frac{6}{a_n + 2}$ with $a_1 = 1$ . Prove by induction that ...
1
vote
3answers
60 views

Proof of the inequality $n(n-1)\dots (n-k+1)>(\frac{n}{2})^k$

I am a little confused about this claim. This is part of a proof in Rudin's analysis book. He uses this claim as a fact without further proofs. Claim If $n>2k>0$ and $n,k\in \mathbb{N}$, then $...
0
votes
1answer
33 views

Prove $\prod_{k=2}^N\left(1-\frac{2}{k^3+1}\right)~=~\frac23\left(1+\frac1{N(N+1)}\right)$

I am struggling to verify the following $$\prod_{k=2}^N\left(1-\frac{2}{k^3+1}\right)~=~\prod_{k=2}^N\left(\frac{k^3-1}{k^3+1}\right)~=~\frac23\left(1+\frac1{N(N+1)}\right)$$ I tried to use ...
0
votes
2answers
41 views

On Proving The nth odd number is 2n − 1 Through Induction, And A Few Extensions

What I've done so far is to prove it for the n+1th number: $(2n-1)+2=2(n+1)-1$. Because any odd number +2 is equals to the next odd number. And in the proof, it is given that 2n-1 is an odd number. ...
3
votes
2answers
100 views

Proving $\sum_{j=0}^n (-1)^j {n \choose j} F_{s+2n-2j} = F_{s+n} $, where $F_n$ is the $n$-th Fibonacci number

$$\sum_{j=0}^n (-1)^j {n \choose j} F_{s+2n-2j} = F_{s+n} $$ ($F$ is Fibonacci number). I have been trying to prove this by mathematical induction. First I assume this is true for n. If I ...
1
vote
1answer
30 views

Induction proof of Zeckendorf's theorem for Narayana's sequence

I am stuck doing the proof by induction of the following equation: $$ 4 M_n = M_{n+3} + M_{n-1} + M_{n-6} + M_{n-7} $$ $M_n$ is defined by: $$M_n= M_{n-1} + M_{n-3}$$ I've executed the proof for the ...
0
votes
0answers
55 views

Prove by mathematical induction that $n^2 > n$ for all $n \geq 2$

Prove by mathematical induction that $n^2 > n$ for all $n \geq 2$. My attempt: When $n=2$ LHS , $2^2 =4$ RHS , $2$ When $n=2$, LHS $>$ RHS Assume true for $n=k$ $k^2>k$ RTP true for $...
3
votes
1answer
46 views

How to proceed on Induction problem involving permutations

Here’s the problem. Given two non-decreasing sets of $n$ real numbers, $a_1 \leq \cdots \leq a_n$ and $b_1 \leq \cdots \leq b_n$. Define $$Q(\ell_1, \cdots , \ell_n) = \sum_{i=1}^n (a_i - b_{\ell_i})^...
0
votes
1answer
59 views

Terry Tao's strong induction formulation

So I began to read Terry Tao's "Analysis 1" and I got confused by his strong induction formulation. The way he puts it is: "Let $m_0$ be a natural number, and let $P(m)$ be a property pertaining to an ...