Stack Exchange Network

Stack Exchange network consists of 175 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

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.

1
vote
2answers
45 views

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}$. ...
1
vote
1answer
28 views

Understanding Proof about Continued Fraction convergent sequences

I copied a proof from lecture and don't understand the end of it. It is intro number theory on continued fractions. Hopefully someone can explain it to me Background: The sequences {$h_n$} and {$k_n$...
1
vote
1answer
52 views

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}" ...
0
votes
0answers
30 views

Rewrite a cubic summation [on hold]

how do you write $$\left(\sum_{i=1}^{k}{ i^3}\right) + (k+1)^3$$ as a single summation?
3
votes
2answers
68 views

Prove by mathematical induction $4^n > n+1$

Prove the following by mathematical induction: $4^n > n+1$, for all integers $n ≥ 1$ Step 1: $n=1$: LHS $= 4^{(1)} = 4 $ RHS $= (1) + 1 = 2$ LHS > RHS. ∴ $P(1)$ is true. Step 2: Assume $P(k)$...
2
votes
1answer
49 views

Proof by mathematical induction with the problem $40(2n)! ≥ 30^n$

I want to start by saying that I have far less trouble handling a non-inequality induction problem. I really don't understand the steps to take to get to the desired end product with these inequality ...
0
votes
1answer
21 views

Induction/More so A question about simplifying square roots

Ok I Get everything up until the point where it says. k $\sqrt{k+1}$ + $\sqrt{k+1}$ = (k+1) $\sqrt{k+1}$ How in the world did they get there? Or am I missing something else
0
votes
1answer
59 views

Induction question about partitioning with a condition

We have $n$ students which are in $k$ classes. We know that between each two classes, there exist two persons A and B who know each other. Prove that we can put students in $n-k+1$ groups such that ...
0
votes
1answer
18 views

Prove by induction that $\frac{d^ny}{dx^n} = n3^{n-1}e^{3x}+x3^ne^{3x}$ for the equation $y(x)=xe^{3x}$

I have been solving this question, and I proved n=1, assumed n=k is correct and attempted to solve n=k+1. I got to the point where $$\frac{(d^{k+1}y)}{dx^{k+1}} = \frac{d⋅d^ky}{dx⋅dx^k}$$. Although I ...
1
vote
2answers
64 views

Using induction to prove a sequence $a_1=1$ and $a_{n+1}=3-\frac{1}{a_n}$ is increasing

I have a sequence defined by $a_1=1$ and $a_{n+1}=3-\frac{1}{a_n}$. I need to use induction to show that the sequence is increasing and $a_n<3$ for all $n$. Also to deduce that $a_n$ is ...
1
vote
1answer
57 views

How to prove Ky Fan Inequality using Forward-Backward Induction?

The classical version of the inequality is: $${\frac {{\bigl (}\prod _{{i=1}}^{n}x_{i}{\bigr )}^{{1/n}}}{{\bigl (}\prod _{{i=1}}^{n}(1-x_{i}){\bigr )}^{{1/n}}}}\leq {\frac {{\frac 1n}\sum _{{i=1}}^{...
3
votes
1answer
35 views

fibonacci and lucas numbers induction

I'm having trouble proving by induction that this following Fibonacci-Lucas equation $$F_{2n+k} = F_n L_{n+k} + (-1)^n F_k \tag{*}$$ is true, given that $$F_{2n} = F_nL_n$$ and $$F_{2n+1} = ...
0
votes
3answers
38 views

Proof that an even number plus an odd number is equals to an odd number [on hold]

How can I prove using an induction technique that an even number plus an odd number is always equals to an odd number? Thanks in advance!
2
votes
0answers
60 views

Induction Proof: Define the sequence $ \ \ T_1, T_2, T_3,…\ \ $ by $\ \ T_1=T_2=T_3=1 \ \ $ and $ \ \ T_{k+1}= T_{k}+T_{k-1}+T_{k-2}$.

I would appreciate if someone could comment my solution of the task below: Define the sequence $ \ \ T_1, T_2, T_3,...\ \ $ by $\ \ T_1=T_2=T_3=1 \ \ $ and $ \ \ T_{k+1}= T_{k}+T_{k-1}+T_{k-2}$. ...
-1
votes
1answer
41 views

I need help with induction proof [on hold]

Prove by induction if Chicken McNuggets are sold in quantities of 6, 9, and 20, then the largest amount that cannot be purchased is 43.
2
votes
3answers
57 views

Induction Proof for Sequences

Given a sequence $s_k=s_{k-1}+6k$, where $s_0=7$. Question: First, find the closed formula for the $n$-th component of this sequence by hand and then prove that your formula is correct My attempt: ...
-1
votes
2answers
45 views

How do I prove this by induction? With the induction on n [on hold]

How do I prove this with mathematical induction, the entire problem is like a Putnam/coffin problem, where the solution is almost impossible.I proved the basis case with a_0. But after that, when I ...
-3
votes
1answer
26 views

prove by induction that 2^n/n! < 4/n [on hold]

How do I do this? I know how to do the base case but I can't figure out how to do the next steps.
2
votes
3answers
67 views

Prove that if $n \in \omega$ then $n \notin n$

Prove that if $n \in \omega$ then $n \notin n$. I'm trying to do it by induction. Consider $S=\{n \in \omega : n \notin n\}$ $0 \in S$: $\emptyset \notin\emptyset $ $i\in S \Rightarrow s(i) \in S$: ...
1
vote
1answer
22 views

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
vote
2answers
37 views

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}}...
1
vote
1answer
45 views

Demonstration by induction without using the induction hypothesis

my definition of sum: $\sigma_n(0)=n$ $ \sigma_n(s(m)) = s(\sigma_n(m))$ in which $\sigma_n$ is obtained from the recursion theorem. I want to show directly from the axioms of peano that if $n,m \...
1
vote
1answer
43 views

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)}+...
3
votes
2answers
65 views

Proof - Graph Connectedness

Let $n\ge2$ be an integer. Let $G$ be a graph with $n+1$ vertices and more than ${n \choose 2}$ edges. Show that $G$ is connected. Here's my attempted solution to the above problem: Induction on $...
0
votes
1answer
22 views

Prove the statement, For all integers $n ≥ 0$, $y_n = 3 * 2^n + 4^n$ where $y_0 = 4, y_1 = 10$ and when $n ≥ 2$, $y_n = 6y_{n-1} – 8y_{n-2} $

So approaching this problem For all integers $n ≥ 0$, $y_n = 3 * 2^n + 4^n$ where $y_0 = 4, y_1 = 10$ and when $n ≥ 2$, $y_n = 6y_{n-1} – 8y_{n-2} $ I realise that is probobly needs to be proved ...
2
votes
1answer
31 views

Show that if $x_{0}=1$ and $x_{n+1}=1+\frac{1}{x_n}$ then $|\varphi-x_n|\leq \frac{1}{\varphi^{n+1}}$ and $x_n\rightarrow \varphi$

I have tried out induction, there are some Formulars of phi that I have understood. For example $\varphi=1+\varphi^{-1}$ and $\varphi^2-\varphi=1$. This is my attempt so far. I want to Show the ...
0
votes
0answers
41 views

Is this a valid proof of why induction works?

If P(n) is true for 1, and it is true for k+1 whenever it is true for k, shouldn't it be clear that P(n) is true for any natural number n, since we can let k=1, then k=2, and continue this process ...
0
votes
1answer
37 views

Show, with induction that $1^2 + 2^2 + … + n^2 = \frac{n(n+1)(2n+1)}{6}$ [duplicate]

Show, with induction that $1^2 + 2^2 + .... + n^2 = \frac{n(n+1)(2n+1)}{6}$ My attempt Case 1: n = 1 $LHS = 1^2$ $RHS = \frac{(1+1)(2+1)}{6} = \frac{2*3}{6} = 1$ Case 2: n = p $LHS_{p} = 1^2 + ...
0
votes
0answers
9 views

Functor to represent directed acyclic graphs for (co)induction

The general theory of induction and coinduction is usually presented in terms of initial algebras and finial coalgebras for certain endofunctors (monads) on the category of sets. (See for example ...
1
vote
1answer
60 views

Proof that the real number $\text {fin} \mathcal M$ has an additive inverse using induction.

This question regards the proof outlined on page 138 of Fundamentals of Mathematics, Volume 1 Foundations of Mathematics: The Real Number System and Algebra; Edited by H. Behnke, F. Bachmann, K. Fladt,...
1
vote
0answers
30 views

Simple Proof of Binomial Theorem for Negative Integer Powers

There's a vast amount of clutter on the internet about this which I've been trawling through but it does not answer exactly what I'm asking which, because superficially similar questions have been on ...
0
votes
1answer
43 views

How to show $\forall n \in \mathbb{N^*}, (\frac{2n}{3}+\frac{1}{3})\sqrt{n} \leq \sum_{k=1}^{n}\sqrt{k}$?

How to show by induction $\forall n \in \mathbb{N^*}, (\frac{2n}{3}+\frac{1}{3})\sqrt{n} \leq \sum_{k=1}^{n}\sqrt{k}$ Thanks for heping me :)
0
votes
1answer
39 views

How to use induction to show how to construct a graph with $2n$ nodes and $n^2$ edges such that the graph as exactly one, unique, complete pairing?

Given an undirected graph $G=(V,E)$, use mathematical induction to show how to construct a graph with $2n$ nodes and $n^2$ edges such that the graph has exactly one, unique, complete pairing. ...
0
votes
1answer
50 views

Inequalities involved in the proof of transcendence of $[0,10,10^{2!}, \dots]$

In proof of transcendence of the simple continued fraction $[0,a_1,a_2, \dots]$ in which $a_k=10^{k!}$ (Hardy, et al's Theory of Numbers) it uses the following two inequalities: i. $(1+\frac{1}{10})(...
1
vote
4answers
59 views

Finding an explicit formula for $a_1 := 1, a_{n+1} := 1 + \sum_{i=1}^{n} ia_i$

I need to find the formula for the general term of the recurrence relation $$a_1 := 1, a_{n+1} := 1 + \sum_{i=1}^{n} ia_i$$ I predicted the general term is $a_n = n!$, and I've tried to prove it by ...
1
vote
3answers
49 views

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 ...
-1
votes
1answer
34 views

Find an integer $N$ such that $2^n > n^4$ whenever n is an integer greater than N.

Was just hoping to validate my proof: Let $n=16\Rightarrow 2^{16}>16^4\Rightarrow 65536>65536$. Prove $P(n)=2^n>n^4$ whenever $n>16$. Basis Step: $P(17)=2^{17}>17^4\Rightarrow 131072&...
1
vote
4answers
65 views

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\...
1
vote
1answer
20 views

How to simplify this expression to get the target expression by induction.

I'm doing the OCR MEI further maths Pure 1 2017 exam paper, checked the mark scheme but i still dont understand the working out of the simplification of the expression. There is one question that i ...
0
votes
1answer
45 views

Is the exclusion of infinite decimal expressions of the form $a_0.a_1\dots{a_n}\bar{9}$ logically necessary?

My question really is as simple as: Is the exclusion of infinite decimal expressions of the form $a_0.a_1\dots{a_n}\bar{9}$ logically necessary? The obvious alternative would be $a_0.a_1\dots{a_n}\...
3
votes
2answers
68 views

There's an equivalence of simplicial categories $\Delta \to \tilde{\Delta}^{\text{op}}$.

Let $\Delta$ be the simplicial category, that is, the category of finite totally ordered sets and order-preserving maps. Let $\tilde{\Delta}$ be the subcategory where objects are those of $\Delta$ ...
1
vote
1answer
22 views

Trouble finding the formula for f(n) of a recursive function.

I've been working on this problem: Determine whether each of these proposed definitions is a valid recursive definition of a function f from the set of nonnegative integers to the set of integers. If ...
1
vote
0answers
19 views

Is this a complete proof by induction?

I am trying to prove the following conjecture. $$\sum_{k=0}^{n}(4k+3)^{m}\, T(n,k) = \sum_{k=0}^{n}(4(n-k)+1)^{m}\, T(n,k)$$ where $T(n,k)$ are a sequence of numbers (it isn't really relevant to ...
0
votes
1answer
15 views

Prove that [n / 3] = O (n)

How should I start by proving this? I know that for very large N values ​​the difference between the two numbers will be minimal, but I do not know how to prove it to my concrete math teacher.
0
votes
1answer
77 views

Constructive Imduction

An airplane crashes on an island in the middle of nowhere. The $n$, ($n \geq 1$) passengers all end up apart from everyone else. We call each passenger a group. The passengers start wandering around. ...
1
vote
2answers
56 views

Constructive Mathematical induction

$r_n = 2r_{n-1} + 5r_{n-2}$ Where $r_1 = r_2= 2$, Assume $r_n \le ab^n$ (primarily upper bound b as tightly as possible, and secondarily upper bound a as tightly as possible. Use Constructive ...
0
votes
0answers
55 views

Proof by induction $\gcd(2^n-1,2^m-1)=2^{\gcd(n,m)}-1$

It is asked to perform a proof by induction over a variable $k$, which is $k=m+n$ and to use a given equation: $\gcd(a,b)=\gcd(a+b,b)=\gcd(ac+b,a)$, which might help throughout the proof-writing. ...
0
votes
1answer
26 views

Prove that if G — (V, E) is an arbitrary bipartite graph, then $|E| \leq |V|^2/4$ using induction [duplicate]

let $n=\mid V\mid$ base case: let $n=0$. Thus lemma becomes vacuously true since both bipartitions will contain the empty set thus not a bipartite graph. Inductive step: let $k\in\mathbb{N}$, ...
2
votes
1answer
62 views

An apparently harmless exercise concerning induction

I'm trying to solve Exercise 12 at page 14 from "A Concrete Introduction to Higher Algebra" by L. Childs. The text is the following. Let $b \in \mathbb{R}, b \ge 2$. Prove that $$(b^n - 1)(b^n - b)(b^...
1
vote
2answers
26 views

Prove $2^n$ is smaller than binomial coefficent of $2n$ over $n$

I need to show that $\binom{2n}{n} \geq 2^n$. I'm required to do this by using induction. For $n=1$ this is rather easy. I just don't get very far when going to the next step for $n+1$. Is there a ...