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
2answers
34 views

Proving a Recursive Formula

I know there are some questions on this site about how to find a recursive formula, but I've already found the formula. I'm doing an assignment (http://mathstat.dal.ca/~svenjah/math2112/Assign6.pdf) ...
0
votes
0answers
35 views

Principle of infinite descent

I'm trying to prove the following: "It is not possible to have a sequence of natural numbers which is in infinite descent. (Hint: assume for sake of contradiction that you can find a sequence of ...
0
votes
1answer
32 views

A proof by induction and trigonometry

Do you know how to prove that $cos(\frac{X}{2}) + cos(\frac{3x}{2})... + \frac{cos(2n-1)}{2} = \frac{sin(nx)}{(2sin1/2x)}$ with induction? I have tried with n = 1 which gives $cos \frac{x}{2} = ...
2
votes
2answers
53 views

Number Theory- Mathematical Proof

I am trying to prove a theorem in my textbook using another theorem. What I need to show that if a,b, and c are positive integers, show that the least positive integer linear combination of a and b ...
2
votes
1answer
13 views

Binary addition preserving Hamming weights

Let $x,y$ be two $n$-bit strings, with Hamming weights (number of $1$ bits) equal to $w_{1},w_{2}$, respectively. Let $z$ be the binary representation of the sum $x+y$, where we interpret $x$ and $y$ ...
0
votes
1answer
151 views

King Arthur and knights at the round table puzzle

Can you help me with this math problem : Each of the $K$ knights from the round table needs to choose a card which is marked with a number from $1$ to $N$, $N \ge K$. The cards all have a different ...
0
votes
0answers
21 views

Prove equality of Fibonacci sequence

Let $u(n)$ — the Fibonacci sequence. Prove that $$u(1)^3+...+u(n)^3=\frac{ 1 }{ 10 } \left[ u(3n+2)+(-1)^{n+1}6u(n-1)+5 \right].$$ I suppose we need prove that equality by iduction in $n$. ...
0
votes
4answers
79 views

Prove by using Mathematical induction (sum of the first $n$ odd numbers is $n^2$)

$$1+3+...+(2n-1) = n^2 for\quad all\quad n∈N$$ Been watching youtube vidoes but still confused. Step 1: Show that n=1 is true (Initial value) LHS = 2(1)-(1) = 1, RHS = $1^2$=1 therefore LHS=RHS. ...
0
votes
2answers
40 views

Proving 9 divides a cubic by Induction

I have just started to cover induction mathematics in my Discrete Mathematics class and I'm a little confused as to where to go with this problem. Am I on the right track? Prove that 9 divides (n^3 ...
2
votes
2answers
117 views

Mathematics induction (exponential divisible by 2304)

$7^{2n} -48n - 1$ is divisible by 2304 for all $n \in N$ so I did, P(n) : $7^{2n}-48n-1=2304k$ (k meaning there is an integer which will depend on n) Prove base case $P(1): 7^2 - 48(1)-1 = 0$, ...
0
votes
1answer
297 views

Induction to prove regular expression

Prove that is if S and T are any regular expressions over the one-letter alphabet, (for example: Σ = {a}), and if n is any natural, then the languages (ST)^n and (S^n)(T^n) are equal. I have to use ...
1
vote
1answer
27 views

Lines in the plane from Concrete Mathematics. How many bounded regions are there?

I'm studying Concrete Mathematics by Donald Knuth. While doing the warmup questions, from the recurrence chapter, I stumbled upon an interesting problem. I have an intuition about the solution but I ...
9
votes
6answers
361 views

Principle of Transfinite Induction

I am well familiar with the principle of mathematical induction. But while reading a paper by Roggenkamp, I encountered the Principle of Transfinite Induction (PTI). I do not know the theory of ...
1
vote
3answers
161 views

Using induction to study the sequence $\sqrt{6} , \sqrt{6 +\sqrt{6}}, \dots$

For the given sequence $\sqrt{6} , \sqrt{6 +\sqrt{6}},\sqrt{6+\sqrt{6+\sqrt{6}}} $ ... Use induction to show the sequence is bounded above by 3 Use induction to show $x_n $ is increasing Find the ...
2
votes
2answers
52 views

Prove by Induction ( a Limit)

I think I did much wrong with this exercise... I think I solve it , in such case I'd like to know others way to solve... (Introduction to calculus and analysis vol 1, Courant page 113, exersice 16 ) ...
0
votes
2answers
26 views

proof by induction for golden ratio and fibonacci sequence

I have to prove the following equation by induction for $$x = \phi$$ I am stuck and I don't know how to proceed. This is the equation $$ \phi ^n = f_n\phi + f_{n-1} $$ where $f_n$ is the nth term ...
6
votes
3answers
422 views

Some trouble with the induction

Prove, that for any positive integer $n \geqslant 2$ we have the inequality $$ \frac{ 4^n }{ n+1 } < \frac{ (2n)! }{ (n!)^2 }.$$ For $n=2$ the inequality is true. Directly just take and ...
3
votes
2answers
36 views

Prove by induction that for the Fibonacci numbers $F(n)$ with $n \ge 6$, $F(n) \ge 2^{n/2}$

Prove by induction that $F(n) \ge 2^{n/2}$ for $n \ge 6$ I've done the following steps: 1) Base case: $F(6) = 8$, $2^{0.5 \cdot 6} = 8$, base case proved. 2) Induction: let's assume that $F(k) ...
-6
votes
0answers
36 views

Prove by induction this notation [closed]

Prove by induction? For $n\geq0$, $$\sum_{i = 0}^n (n i+2)^2={1 \over 3}(n+1)(2n+1)(2n+3)$$ Please help me.
1
vote
0answers
39 views

Verification of Basic Proof in Spivak Calculus (Induction)

I have began working through Spivak's Calculus book and trying to do the problems at the end of the chapters. I am rather new to proof, so forgive the naivety of this type of question. I am wanting ...
1
vote
1answer
70 views

Harmonic numbers, proof that h2^k >= 1+(k/2) with induction

I'm just starting with the concept of proving mathematical statements with induction. The complete exercise with solution can be found under: ...
1
vote
1answer
18 views

Confusion regarding differences between strong induction and simple induction

I don't know how to prove that any proof by induction is also proof by strong induction nor any proof by strong induction can be converted into a proof by simple induction? An example would be useful ...
6
votes
2answers
49 views

Convergence and divergence depending on whether $n$ is odd or even

It is part of one problem I am working on: I want to prove the following conjecture ($x\ne q\pi$ where $q\in\Bbb Q$) $$\sum_{n=1}^{\infty}\frac{\sin^{2k-1}(nx)}{n^{\alpha}}\quad\text{converges ...
6
votes
2answers
81 views

Proving that $x^m+x^{-m}$ is a polynomial in $x+x^{-1}$ of degree $m$.

I need to prove, that $x^m+x^{-m}$ is a polynomial in $x+x^{-1}$ of degree $m$. Prove that $$x^m+x^{-m}=P_m (x+x^{-1} )=a_m (x+x^{-1} )^m+a_{m-1} (x+x^{-1} )^{m-1}+...+a_1 (x+x^{-1} )+a_0$$ on ...
-1
votes
0answers
49 views

Induktion with a k term [on hold]

Hi again i am having trouble with another induction number that is $\sum_1^n$ 1/1+2...+k = 2n/n+1 For n = n+1 I have LHS: 2/(k(k+1) * 2n/(n+1) which i have expanded to 2/(n+1)(n+1)+1* ...
0
votes
3answers
40 views

Question regarding an induction proof

I am stuck on a question regarding induction. I know that we are supposed to solve it using 3 steps: the base step, the n= p step and n = p+1. The question is prove that ...
3
votes
1answer
118 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: ...
-1
votes
3answers
32 views

Induction well ordering principle [duplicate]

Can someone help me with the following question. I have mangaged to solve this question using well ordering prinicple but cant proof it by the induction method. I cant proof that n+1 holds in the ...
4
votes
3answers
135 views

Proof of Equation by Well Ordering Principle

I have an assignment question Prove by either the Well Ordering Principle or induction that for all nonnegative integers $n$: $$\sum_{k=0}^n k^3 = \left(\frac{n(n+1)}{2}\right)^2.$$ I am able to ...
-1
votes
1answer
68 views

prove set definition - by induction?

$X\subseteq Z^+$ defined recursively as: $1)$ $3\in X$; and $2)$ If $a,b\in X$, then $a+b\in X$. Prove that $X=\{3k|k\in Z^+\},$ the set of all positive integers divisible by $3$. Induction on the ...
0
votes
0answers
34 views

Proof that all derivatives at zero equal zero [duplicate]

Trying to prove that given $$ f(x)=\begin{cases} e^{-{\frac {1}{x^2}}} & \text{if $x\ne0$}\\[6px] 0 & \text{if $x=0$} \end{cases} $$ that $\ f^{(n)}_{(0)}=0$ for every n$\ \in\mathbb N$ ...
3
votes
3answers
107 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. ...
4
votes
2answers
849 views

Is my induction proof of the handshake lemma correct? (Graph Theory)

I am an high-school senior who loves maths, I decided to taught myself some basic Graph Theory and I tried to prove the handshake lemma using induction. While unable to find any proofs similar to the ...
1
vote
2answers
67 views

How can I show that $n^{n+2}<(2n)!$ for any integer $n$.

When I was try to show that the series $$\sum_{n\in\mathbb{N}} \frac{n^n}{(2n)!}$$ is convergent using comparison test, I stuck at the point $$n^{n+2}<(2n)!$$ I think it can be show using ...
4
votes
4answers
167 views

Prove that $1+a+a^2+\cdots+a^n=(1-a^{n+1})/(1-a)$.

I have problem. Prove this using Mathematical Induction. I am a newbie in Mathematics. Please help me. $$1+a+a^2+\cdots+a^n = \frac{1-a^{n+1}}{1-a}$$ This is my way for get the proof Basic ...
0
votes
1answer
83 views

Prove that a tree in which every vertex has degree at most 2 is a simple path

Prove that a tree in which every vertex has degree at most 2 is a simple path. More precisely: Let $G = (V,E)$ be an undirected tree, with $|V| = n \geq 1$ and assume that every vertex has degree ...
3
votes
5answers
108 views

proving that $(n-1)^n>n^{n-1}$ [duplicate]

I want to prove that $(n-1)^n>n^{n-1}$, for $n>4$, $n$ is an integer. So I divided by $n^n$ and got: $(1-\frac{1}{n})^{n}>\frac{1}{n}$ I know that ...
0
votes
2answers
71 views
0
votes
1answer
38 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 ...
4
votes
5answers
68 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 ...
1
vote
3answers
81 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
1answer
19 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 ...
2
votes
2answers
34 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
votes
2answers
76 views

Using induction to verify the formula for a summation $\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}6$ [duplicate]

Problem 4. use the principle of induction to verify: $$\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}6$$ base case is obviously easy, but I don't know how to prove the inductive case
5
votes
2answers
710 views

Using strong induction to get the AM-GM inequality for $2^n$ numbers

The arithmetic mean of $k$ numbers $a_1, a_2, \ldots, a_k$ is their average $\frac{a_1+a_2+\cdots+a_k}{k}=AM$. Their geometric mean is $\sqrt[k]{a_1a_2\cdots a_k}=GM$. I am asked to show this: Use ...
4
votes
3answers
1k views

Proving Inequality using Induction $a^n-b^n \leq na^{n-1}(a-b)$

I was trying to prove this inequality using induction, but couldn't do. Question: Suppose $a$ and $b$ are real numbers with $0 < b < a$. Prove that if $n$ is a positive integer, then: ...
0
votes
2answers
74 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
40 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
78 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 ...