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

0
votes
3answers
225 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 ...
3
votes
2answers
58 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
58 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
106 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
2answers
100 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' ...
1
vote
4answers
86 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
250 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
3answers
85 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
39 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
35 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 ...
1
vote
0answers
93 views

Inductive proof about Jensen's inequality

Problem 6 (Jensen's inequality). Let $f: I \longrightarrow \mathbb{R}$ be a concave up function, $I \subset \mathbb{R}$ an interval, and $\lambda_1, \dots, \lambda_n \in (0, \infty)$ positive real ...
1
vote
5answers
140 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 ...
0
votes
4answers
216 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
51 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 ...
2
votes
9answers
158 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
3answers
124 views

The necessity of the axiom of induction

$\underline{First\ question}$ Let $P(n)$ be a proposition about $n$. In standard mathematical induction, we require: (1)$P(0)$ holds. (2)If $P(n)$ holds, $P(n+1)$holds. Here we use "the axiom of ...
0
votes
1answer
73 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 ...
1
vote
1answer
66 views

prove by inductive step [duplicate]

I have some problem to prove this statement by the Principle of mathematical Induction. $$\sum_{i=0}^{n} \binom{n}{i} = 2^n.$$ So I begin with the base step. For $n=0$, $$\sum_{i=0}^{0} \binom{0}{i} ...
2
votes
4answers
3k views

proof by induction: sum of binomial coefficients $\sum_{k=0}^n (^n_k) = 2^n$

Question: Prove that the sum of the binomial coefficients for the nth power of $(x + y)$ is $2^n$. i.e. the sum of the numbers in the $(n + 1)^{st}$ row of Pascal’s Triangle is $2^n$ i.e. prove ...
2
votes
2answers
105 views

Proof by induction that $1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$ [duplicate]

I am trying to understand how to do proof by induction for inequalities. The step that I don't fully understand is making an assumption that n=k+1. For equations it is simple. For example: Prove ...
0
votes
1answer
86 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$, ...
6
votes
1answer
129 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 ...
2
votes
1answer
116 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 ...
0
votes
2answers
78 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)$$
3
votes
1answer
98 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 ...
1
vote
1answer
64 views

How to justify “two-dimensional” induction

Suppose I have a statement $p(m,n)$ where $m,n \in \mathbb{N}$ that I want to prove. Suppose I have proofs of the following: $p(1,n)$ is true for all $n \in \mathbb{N}$. $p(m,1)$ is true for all $m ...
0
votes
2answers
40 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 ...
5
votes
2answers
86 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 ...
4
votes
2answers
44 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 = ...
1
vote
2answers
31 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 ...
0
votes
1answer
43 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
47 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 ...
2
votes
1answer
79 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 ...
4
votes
2answers
124 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
102 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 ...
0
votes
2answers
34 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
47 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
256 views

How to prove that $9^n - 8n - 1$ is divisible by $64$ for $n\ge 0$?

My textbook provided the following proof: Base case: When $n=0, 9^n-8n-1=0=64\cdot0$, so $64\mid\left(9^n-8n-1\right)$. Induction step: Suppose that $n\in\mathbb N$ and ...
1
vote
1answer
329 views

prove weak induction implies strong induction

So trying to prove: i) $[t(n_0)\wedge \forall_n[t(n)\rightarrow t(n+1)]\Rightarrow \forall_{n_0\le n}t(n)]$ $\Rightarrow$ ii) $[s(n_0)\wedge s(n_1)\wedge\cdots \wedge ...
4
votes
4answers
112 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
1answer
38 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
55 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?
2
votes
3answers
134 views

Prove by induction that $G(n)=2^n$

I have a task to solve with algorithm, which is writing all the binary numbers. I wrote the recurrence relation below, as I count the few first values: $$G(n) = \begin{cases}1&\qquad n = 0\\ 2G(n ...
0
votes
2answers
67 views

Prove by induction that for a natural number a there exists integers $x, y$ where $a = 7x + 2y?$

I am trying to get my head around induction at the moment and found this problem in a textbook. I think that I should be doing induction on $a$, but I can't even see where to start the proof.
20
votes
5answers
239 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 ...
3
votes
6answers
101 views

Using induction prove $(n^3)-n$ is divisible by 3 whenever n is a positive number.

I am not sure if I am doing this right, but I have this: There exists an integer $k$. $2k =$ positive number $(2k)^3 - 2k$ [*And this is where I get lost. How does one prove this?]
0
votes
2answers
144 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
42 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 ...
3
votes
2answers
80 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
vote
2answers
19 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 ...