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

learn more… | top users | synonyms

3
votes
1answer
40 views

Induction Proof: $2$ divides $n^2 + n$ for each $n \in \mathbb{N}$

So I am looking at some induction questions and I am trying to solve them on my own but I am getting stumped and frustrated. There was a previous question question that was answered, but I changed it ...
0
votes
1answer
78 views

Prove that a $k$-degenerate graph is ($k+1$)-colorable

A graph is $k$-degenerate if every induced subgraph contains a vertex of degree at most $k$. How can I prove that a $k$-degenerate graph is ($k+1$)-colorable?
1
vote
4answers
40 views

Proving recurrence by mathematical induction

$f(1)=1,$ $f(n)=2f(n-1)+3$ ($\forall n>1$) has the following closed form solution $f(n)=2^{(n+1)}-3$ I understand that I can simply show that the recurrence is equal to $2^{(n+1)}-3$,but not ...
2
votes
2answers
50 views

Proof by contradiction and mathematical induction

$\sum_{i=1}^n {2\over3^i}={2\over3}+{2\over9}+\dots+{2\over3^n}=1-{({1\over3})^n}$ I had this problem in class and we proved using 2 different methods: contradiction and mathematical induction. I ...
0
votes
0answers
29 views

Mathematical induction, sum [duplicate]

Problem: Prove the following by using the Principle of Mathematical Induction: $$1+2+2^2+...+2^{(n-1)}=2^n-1$$ I can prove it for $n=1,$ but I cannot understand what to do next. I would be truly ...
1
vote
3answers
68 views

Prove by induction: $\sum\limits_{i=1}^{n}(4i+1) = 2n^2 + 3n$

Prove by induction: $$\sum\limits_{i=1}^{n}(4i+1) = 2n^2 + 3n$$ It's just the numbers that confuse me; I know how to do a simple induction proof that first for $p(k)$ and then for $k+1$ etc but ...
0
votes
2answers
37 views

Prove by math induction

$\forall n \geq 2$ $\frac{7}{9} \times \frac{26}{28} \times \ldots \times \frac{n^3 -1}{n^3 + 1} = \frac{2}{3} \times (1 + \frac{1}{n(n+1)})$ After basis step i went this far: $ ...
1
vote
0answers
28 views

Induction Proof from Thomas Judson book on abstract algebra

I'm trying to prove $$^n\sqrt{a_1\times a_2\times...\times a_n}\leq \frac{1}{n}\sum_{k=1}^na_k, \quad a_i\in \mathbb{Z}^+$$ by Induction. The case is true for $n=1$ so I assumed true for $n=k$. I then ...
2
votes
1answer
85 views

Quantifier-free induction and comparison with $\sqrt{2}$

I am trying to understand quantifier-free induction in the system called PRA - primitive recursive arithmetic which states the following: $$ \frac{ \varphi[0] \quad \varphi[n] \implies ...
0
votes
4answers
68 views

Prove by induction that sum of an odd number of odd numbers is odd

Prove by induction that if $n$ is odd and $a_1,\,\cdots,\,a_n$ are odd, then $\begin{aligned}\sum_{i = 1}^n a_i\end{aligned}$ is odd. Progress: If $n = 1$ then $\sum_{i = 1}^1 a_i = a_1$, so the ...
0
votes
1answer
42 views

Prove by induction $(\frac{n}{e})^n<n!<e(\frac{n}{2})^n,n\in \mathbb{N}$

$n!>(\frac{n}{e})^n$ $$(n+1)!=n!(n+1)>(\frac{n}{e})^n(n+1)=(\frac{n+1}{e})^{n+1}\times \frac{(\frac{n}{e})^n(n+1)}{(\frac{n+1}{e})^{n+1}}>(\frac{n+1}{e})^{n+1}$$ This implies, but I think ...
1
vote
1answer
40 views
+50

Problem with understanding the induction when proving Sauer Lemma.

I will replicate the proof here which is from the book "Learning from Data" B(N, k) is the maximum number of dichotomies on N points such that no subset of size k of the N points can be shattered by ...
1
vote
5answers
129 views

Show that $30 \mid (n^9 - n)$

I am trying to show that $30 \mid (n^9 - n)$. I thought about using induction but I'm stuck at the induction step. Base Case: $n = 1 \implies 1^ 9 - 1 = 0$ and $30 \mid 0$. Induction Step: Assuming ...
1
vote
2answers
83 views

Version of the Axiom of Induction for Real Induction?

Mathematical induction can be done using the axiom of induction, which is given as a formula written in the language of mathematical logic. Is there a way to express the ideas behind 'real induction' ...
2
votes
9answers
135 views

Proof by induction that $3^n - 1$ is an even number

How to demonstrate that $3^n - 1$ is an even number using the principle of induction? I tried taking that $3^k - 1$ is an even number and as a thesis I must demonstrate that $3^{k+1} - 1$ is an even ...
0
votes
1answer
65 views

prove that $A(n) : \left(\frac n3\right)^n\lt n!\lt \left(\frac{n}{2}\right)^n$ for all $n\ge 6$

prove that $A(n) : \left(\frac n3\right)^n\lt n!\lt \left(\frac{n}{2}\right)^n$ for all $n\ge 6$ first check $n=6$ : $2^6<6!<3^6$ ok then $n\gt 6$ assume $A(m)$ is true, then show ...
0
votes
2answers
82 views

Prove by induction that $\sum_{i=1}^{n} 2i=(n+1)n$, for every positive integer n. [duplicate]

Can anyone explain the concept behind this? I just don't get how I should proceed with it? Like each step, why and how is it done? Prove by induction that $\displaystyle\sum_{i=1}^{n} 2i=(n+1)n$, ...
0
votes
2answers
54 views

Simplifying the product $\prod\limits_{k=1}^n \left(1-\frac1{k^2}\right)$ [duplicate]

Can we simplify the given product to a general law? $$\left(1-\frac{1}{4}\right)\left(1-\frac{1}{9}\right)\left(1-\frac{1}{16}\right)...\left(1-\frac{1}{n^2}\right)$$
2
votes
1answer
93 views

Induction involving lines and regions

If n $\geq$ 2 lines are drawn in the plane, they divide it into a number of regions. Assume that no two lines are parallel and that no three lines meet at a single point. Show that it is possible to ...
7
votes
1answer
112 views

$n$ points in the plane: show there are at least $\lceil \frac{n}{3} \rceil $ different distances between pairs of points

How can I prove that in each group of $n$ points in the plane, such that there are not $3$ points on the same line, there are at least $\left\lceil \frac{n}{3} \right\rceil $ different distances ...
5
votes
2answers
58 views

Induction on finite subset of natural numbers

Can we use induction to prove that a statement $P(n)$ is true for all $n \in \mathbb{N} $ such that $n \leq s$, where $s \in \mathbb{N}$? Specifically, in the second induction step, is it enough to ...
0
votes
2answers
31 views

Induction proof, divisibility

I'm struggling with an induction problem here. I have to prove that $2^{2^n}- 6$ (two to the power of two to the power of $n$ minus six) is divisible by $10$. I already figured some steps and I ...
4
votes
2answers
41 views

Proving a formula using another formula

These questions are from the book "What is Mathematics": Prove formula 1: $$1 + 3^2 + \cdots + (2n+1)^2 = \frac{(n+1)(2n+1)(2n+3)}{3}$$ formula 2: $$1^3 + 3^3 + \cdots + (2n+1)^3 = ...
0
votes
1answer
28 views

Summing series of cosines with binomial coefficients

One part of a STEP-question from 1991 is Prove that $$1 + m \cos 2\theta + \binom {m} {2}\cos 4\theta + \cdots + \binom {m}{r}\cos 2r\theta + \cdots + \cos 2m\theta ~=~ 2^m \cos^m \theta ...
3
votes
1answer
46 views

How to prove that chessboard of size $n \times 3$, with even $n$ and $n \geq 10$, has a closed knight's tour with induction?

I am trying to do an exercise on this topic. I have realized that base cases should be $n = 10$ and $n = 12$. Also I realized that I would need to use $(n+4)\times 3$ during my inductive step. But ...
1
vote
2answers
25 views

Determine the rank of the linear map given by a $n \times n$ matrix , dependend on n. Proof by induction

The task: Let $$ A:= \begin{pmatrix} 1 & a & a & ... & a\\ a & 1 & a & ... &a \\ a & a & ... & a & a\\ ... & ... &... & 1 & a \\ a ...
2
votes
1answer
54 views

Induction implies by well-ordering

A problem in Spivak's Calculus, ch 2-10, asks to prove induction by the well-ordered principle. I have read a number of answers to that question on this site, but I would like to see the proof in a ...
0
votes
2answers
32 views

Proving $T_n = 2\times 20^n + 4\times 8^n$ by mathematical induction

Given that $T_0 = 6$ and that $T_n$ satisfies the recurrence relation $$T_{n+1} = 20T_n - 8^n \times 48$$ I have the equation for any term $n$ to be; $T_n = 2\times 20^n+4⋅8^n$ I want to prove ...
3
votes
2answers
43 views

Part of an induction question

I might have done or not realize something stupid, but I can't seem to prove the following... Inductive hypothesis Assume $\exists$k$\in$N such that P(k) is true. P(k): $\frac{1 \cdot 3 \cdot 5 ...
3
votes
2answers
105 views

Closed knight's tour

I know what a 3x10 looks like, but I cannot seem to find a distinguishable pattern to extend it to a 3x14. The 3x10 pattern I'm using looks like the one at the top right of figure 6 of this paper. ...
2
votes
2answers
97 views

Can every statement be solved by mathematical induction ? (see details below)

I have the following equation system : $$\sum_{i=1}^n a_i^2 = n $$ $$\sum_{i=1}^n a_i=n$$ here the solution is only $a_i$ =1 . Can it be solved by mathematical induction ? I have tried , but have ...
1
vote
1answer
30 views

Having trouble with this proof from Apostol Vol.1, I 4.4 .

If I am correct, it's stating to prove for all n $\ge$ 1, where n is a real number. However, I have only been shown induction proofs for integers. Is it acceptable to prove by assuming a k exists ...
3
votes
1answer
45 views

General term of a sequence $(2-1)(2+1)(3-1)(3+1)…(n-1)(n+1)$

Can we use integrals, and are there some general methods for finding terms of a sequence?
3
votes
1answer
94 views

Inducing representation for groups of order $p^3$

For groups $G$ such that $|G|=p^3$ one can show that $(1)$ $Z=Z(G)\cong C_p$ $(2)$ $G'=Z$ $(3)$ $G/Z \cong C_p \times C_p$ Take any $x \in G/Z$. Then $N=\langle x,Z \rangle$ is an abelian normal ...
16
votes
5answers
116 views

Geometrical interpretation of $(\sum_{k=1}^n k)^2=\sum_{k=1}^n k^3$

Using induction it is straight forward to show $$\left(\sum_{k=1}^n k\right)^2=\sum_{k=1}^n k^3.$$ But is there also a geometrical interpretation that "proves" this fact? By just looking at those ...
0
votes
2answers
61 views

how to prove $2^n = {n \choose 0} +{n \choose 1} + \cdots {n \choose n}$ [duplicate]

I have studying my maths book induction chapter and I found things to solve this but I am failed, somebody help me to solve this problem by simple method of mathematical induction. $$2^n = {n \choose ...
0
votes
3answers
20 views

using mathematical induction problem with n variable as exponent

I am a first year Math student and I am looking at problem in my text book which does not have any answers and I have completely no idea how to do this paticular problem. Show, using mathematical ...
6
votes
4answers
236 views

In-Depth Explanation of How to Do Mathematical Induction Over the Set $\mathbb{R}$ of All Real Numbers?

     I've seen in the answers to a few different questions here on the Mathematics Stack Exchange that one can clearly do mathematical induction over the set $\mathbb{R}$ of ...
1
vote
2answers
17 views

Proving $\sum_{r=1}^n(6r-2)=n(3n+1)$ by induction

A series is defined by $\sum\limits_{r=1}^n(6r-2)$. Use the method of induction to prove that $S_n=n(3n+1)$. I am at the induction step but I am struggling to rearrange $k(3k+1)+6(k+1)-2$ into the ...
3
votes
2answers
71 views

Proving that $\sum_{i=2}^n(5i-4)=\frac{n(5n-3)-2}{2}$ for all $n\geq 1$ by mathematical induction

I have this question: Show, using mathematical induction, that for all natural numbers $n$, $$6 + 11 + 16 + 21 + \cdots + (5n-4) = \frac{n(5n-3)-2}{2}$$ I am confused in that that question states ...
-1
votes
2answers
57 views

Prove $10^{n-1}\le a \lt 10^n$

$$ \forall a \in \mathbb{N}: \quad a = a_{n-1}\times10^{n-1} + a_{n-2}\times10^{n-2} + \dots + a_1\times10 + a_0 \\ a_{n-i} \in \{0;1;2;3;4;5;6;7;8;9\}; \quad a_{n-1} \neq 0 $$ We say that $a$ has ...
3
votes
2answers
175 views

Proof by induction that $x_n>2$ where $x_{n+1}=\frac{2x_n^2 +4x_n -2}{2x_n+3}$

The sequence $x_1$ $x_2$ $x_3$..... is such that $x_1=3$ and $$x_{n+1}=\frac{2x_n^2 +4x_n -2}{2x_n+3}$$ Prove by induction that $x_n>2$ for all $n$. First I proved the base case using $n=1$ as ...
4
votes
4answers
98 views

Proving that $6^{2n+1} + 1$ is divisible by $7$ for $n\geq 1$ by induction

How should I go about solving a problem like this using induction? Would I: First test $(n = 1)$ so that $6^{2(1)+1} + 1 = 6^3 + 1 = 217/7 = 31$. Then assume $(n = k)$ so that you have $6^{2(k) + 1} ...
0
votes
2answers
86 views

Trying to prove $2( \sqrt{n+1}-\sqrt n )< \frac{1}{\sqrt n}<2( \sqrt{n}-\sqrt {n-1})$ and use this to prove… [duplicate]

I am trying to prove this $2( \sqrt{n+1}-\sqrt n )< \frac{1}{\sqrt n}<2( \sqrt{n}-\sqrt {n-1})$ if $n \ge 1$ and using this to prove $2\sqrt{m}-2<\sum^m_{n=1} \frac{1}{\sqrt n}<2( ...
0
votes
2answers
37 views

How to prove the Archimedean property?

The archimedean property states that $$\boxed{~\forall~ ~a,b\in \mathbb{Z}^+~ \exists ~n~|~na\geq b~}$$ I started with disproving .. Suppose $\forall ~\{n,a,b\} \subset \mathbb{Z}^+ , \text{na ...
0
votes
1answer
74 views

Mathematical Induction. Horses made me question my understanding

I recently read about the false inductive proof that all horses are the same colour. There are some mathSE threads about this already (MathSE_thread_1, MathSE_thread_2). After reading this, I now ...
6
votes
5answers
96 views

Inductively prove that any natural number $\ge 12$ can be written as the sum of 4s and 5s

I can intuitively see why this is true: Let us assume $n = \alpha \times 4 + \beta \times 5$ with $\alpha,\beta \in \mathbb{N} \cup \{0\}$. $\forall n \in \mathbb{N} \cup \{0\}$: $n \div 4$ will ...
3
votes
3answers
25 views

Having problem in last step on proving by induction $\sum^{2n}_{i=n+1}\frac{1}{i}=\sum^{2n}_{i=1}\frac{(-1)^{1+i}}{i} $ for $n\ge 1$

The question I am asked is to prove by induction $\sum^{2n}_{i=n+1}\frac{1}{i}=\sum^{2n}_{i=1}\frac{(-1)^{1+i}}{i} $ for $n\ge 1$ its easy to prove this holds for $n =1$ that gives ...
3
votes
1answer
33 views

Proof by induction from Spivak's calculus ch 2- 3b

I was cracking my head over the following proof (by induction) from Spivak's calculus. Givens: $ \binom{n+1}{k}=\binom{n}{k-1}+\binom{n}{k} $ and $ n \ge k $ Task: Proof by induction that $ ...
0
votes
1answer
39 views

Prove using mathematical induction that $n^2 > n+1$ for all $n \ge 2$

I have proved for the initial case $P(2)$ that this is true, but I'm stuck at substituting in $n=k+1$, $(k+1)^2 > (k+1)+1$ = $k^2 + 2k + 1 > k+2$, where do I go from here or have I made a ...