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

2
votes
9answers
136 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
66 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
83 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
64 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
96 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
118 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
61 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
33 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
32 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
58 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
44 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
108 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
99 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
34 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
47 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
95 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
121 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
67 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
21 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
262 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
18 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
177 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} ...
1
vote
2answers
92 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
39 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
84 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
100 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
34 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
40 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 ...
0
votes
1answer
49 views

Limit of $a_{n+1}= \frac{n}{n+1} a_n$

I think that this sequence $$a_{n+1}= \frac{n}{n+1} a_n$$ can be rewritten as $$a_n= \frac{1}{n+1}a_0.$$ Therefore the limit should be $0$. But my proof by induction turns out wrong. Is my idea ...
0
votes
1answer
70 views

How can I prove this statement about square root?

Introduction In computer science there is a field called Formal Methods and Specifications. In this field software designers design softwares by specifying their functionalities in formal methods, ...
14
votes
7answers
208 views

What are statements about the natural numbers where induction is impossible or unnecessary to prove?

I'm looking for statements like "for all natural numbers, ____" where induction would be impossible or unnecessarily complicated. This is for pedagogical reasons. When students first learn induction, ...
0
votes
0answers
23 views

Demonstration of exponentiation with induction

How can you demonstrate that $a^0 = 1$ and that $a^{-n} = (1/a)^n$ using the principle of mathematical induction?
4
votes
1answer
43 views

How many Fibonacci Numbers are in the sequence

I have $I_n = \{2^n + 1, 2^n + 2, 2^n + 3, \dots , 2^{n+1}\}$ and I am trying to prove using induction how many Fibonacci numbers are there. First, the length of $I_n$ is $|I_n| = 2^n$ then for $F_0 ...
1
vote
3answers
105 views

Prove $\frac{1}{n} =\frac{1}{n+1}+\frac{1}{n(n+1)}$ for all integers $n\in\Bbb Z$

I'm pretty sure that we need induction, since it's the format I had to use for previous problems similar to this (it isn't specified that it HAS to be an inductive proof, either, if there is another ...
1
vote
0answers
67 views

Using induction to prove the “hockey stick theorem”

The question we were given was (where $^nC_c$ is $n$ choose $c$): Show, using induction and the fact that $^nC_c + ^nC_{(c+1)} = ~^{(n+1)}C_{(c+1)}$, the "hockey stick theorem": the sum from $k=c$ ...
5
votes
3answers
89 views

Using induction to prove that $n^2 > n + 1$ for $n\geq2$

Use mathematical induction to prove that $n^2 > n + 1$ for all $n\geq2.$ I have proved that it is true for the initial case $n=2$ as $4>3$, and have assumed the statement to be true for $k^2 ...
0
votes
0answers
22 views

Prove Ackermann's function by induction

I have to prove the following property $$A(x,y)>x$$ of Ackermann's function. Do we do the following? We will show that $$A(x, y) \geq A(0, x+y)$$ by induction on $k=x+y$. Base case: For $k=0$ ...
0
votes
1answer
25 views

Proving $F_n \ge (\frac{1}{2}(1+\sqrt{5}))^{n-2}$ for $n \in \mathbb{N}_{>1}$ when $F_n$ is the nth Fibonacci number

Let $F_n$ be defined as the nth Fibonacci number. Prove that $F_n \ge (\frac{1}{2}(1+\sqrt{5}))^{n-2}$ with $n \in \mathbb{N}_{>1}$ My approach thus far was to use induction over $n$. ...
-1
votes
1answer
33 views

Is there an easier way to prove this induction?

Given that $u_1=1$, $u_{r+1} = \frac{2u_r-1}{3}$ Prove using induction that $u_n = 3(\frac{2}{3})^n-1$ Step 1: prove that $u_1=3(\frac{2}{3})^1-1$ $3(\frac{2}{3})^1-1$ $3(\frac{2}{3}) - 1$ $2-1$ ...
2
votes
2answers
54 views

Prove this binomial identity using induction

prove this identity: $(1-x)^{-k} = \sum\limits_{i>=0} \binom {n+k-1} {k-1} x^n $ using induction. Verification for k=1 is trivial. assuming k= i, proving the identity when k=i+1 is something i ...
0
votes
1answer
28 views

Is this a proof that recursive definition of functions indeed defines a function?

Someone asked me how you prove that defining a function recursively actually defines a function, and then I tried to rigorously prove it. Is it right? Let $\mathbb{N}=\{0,1,2,\dots\}$. For any ...
2
votes
6answers
101 views

Prove that $7$ divides $1 + 2^{(2^n)} + 2^{(2^{n+1})}$ by induction

Prove that $7$ divides $1 + 2^{(2^n)} + 2^{(2^{n+1})}$ by induction. I ran into the above problem. The base case $n=1$ gives $21$ which is divisible by $7$. Now assume it is true for $n$. Then for ...