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
3answers
112 views

Identity on Fibonacci numbers: $F_{2n}^2=F_{2n+2}F_{2n-2}+1$?

Let $F_n$ be the Fibonacci Sequence ($F_1=F_2=1, F_{n+2}=F_{n+1}+F_{n}$). Prove that $F_{2n}^2=F_{2n+2}F_{2n-2}+1$. I've tried everything from induction to telescoping series but I haven't got close. ...
0
votes
1answer
43 views

Strong Induction: Prove that sqrt(2) is irrational

This question comes directly out of Rosen's Discrete Mathematics and It's Applications pertaining to Strong Induction. Use strong induction to prove that $\sqrt{2}$ is irrational. [Hint: Let $P(n)$ ...
0
votes
2answers
65 views

How to find whether this series converges or diverges?

Let's suppose I have been given a series that looks like this: $$\sum_{n=1}^n\frac{1\cdot 3\cdot 5\cdot\cdots\cdot(2n-1)}{2\cdot5\cdot8\cdot\cdots\cdot(3n-1)}$$ What I have been thinking of doing ...
3
votes
1answer
125 views

Finalising proof from Humphreys´ “Introduction to Lie Algebras and Representation Theyory”

$L=\mathfrak{sl}(2, \mathbb{F})$ with standard Chevalley basis $(x, \ y, \ h)$ and $a, \ c\in \mathbb{Z}^{+}$. Humphrey gives a Lemma in chapter 26.2 saying: ...
4
votes
5answers
84 views

$p$ divides $n^p-n$

Its very easy to prove $p\mid n^p-n$ for p=3,5,7, it fails for p=9 because $$ (n+1)^9-(n+1)= n^9+9n^8+36n^7+84n^6+126n^5+126n^4+84 n^3+36n^2+8n $$ and $84= 2²\times 3\times7$. Is it true for ...
0
votes
1answer
20 views

Verifying quadratic reciprocity for the Jacobi symbol

I am trying to prove: If $m,n$ are odd coprime positive integers, then $$\Big(\frac mn\Big)\Big(\frac nm\Big)=(-1)^{\large\frac{m-1}2\frac{n-1}2},$$ where $\big(\frac mn\big)$ is the Jacobi ...
1
vote
2answers
38 views

Proving binary integers

This is a very interesting word problem that I came across in an old textbook of mine. So I know its got something to do with binary integers (For ${0, 1, 2, 3}$ we have the representations $0, 1, 10, ...
1
vote
3answers
86 views

Induction Proof: $\sum_{k=1}^n k^2$

Prove by induction, the following: $$\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}6$$ So this is what I have so far: We will prove the base case for $n=1$: $$\sum_{k=1}^1 1^2 = \frac{1(1+1)(2(1)+1)}6$$ We ...
0
votes
2answers
76 views

Explain how the proof is done

A solution of matrix problem appears to be as follows some one explain the following in the solution why is A cube is eliminated and fourth power of A is obtained? In the seventh line In the ...
0
votes
2answers
41 views

Proving if $-1 < x < 1$ then $x^1 + x^2 + \cdots + x^n = \frac{x-x^{n+1}}{1 - x}$

Let $$S_n = x + x^2 + x^3 + \cdots + x^n$$ then $$xs_n = x^2 + x^3 + \cdots + x^n + x^{n+1}$$ This is taken from book "An concise introduction to pure mathematics" : Why does inserting $x$ to ...
0
votes
3answers
95 views

Proving “The sum of n consecutive cubes is equal to the square of the sum of the first n numbers.”

From http://www.themathpage.com/aPreCalc/mathematical-induction.htm states : should : not be : $$1^3 + 2^3 + 3^3 + ... + n^3 = \frac{n^3+(n + 1)^3}{2^3}$$ as everthing to left of equation is ...
2
votes
2answers
44 views

Solution to Fibonacci Recursion Equations

Let the sequence $(a_n)_{n\geq0}$ of the fibonacci numbers: $a_0 = a_1 = 1, a_{n+2} = a_{n+1} + a_n, n \geq 0$ Show that: i) $$a^2_n - a_{n+1}a_{n-1} = (-1)^n \text{ for }n\geq1$$ I try to show ...
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
70 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
29 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
87 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
69 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
45 views

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
88 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
59 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
32 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
30 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
55 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
32 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
117 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
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
248 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 ...