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
62 views

Induction Inequality with Summation [closed]

I can't seem to figure out this problem. Do you have any ideas? For an integer $n > 1$, show that $$ \sum_{k=1}^n {1\over \sqrt{{n^2}+k}} > {{\sqrt{1+{1\over n}}}\over 2} $$
-1
votes
3answers
70 views

Show that ${n\choose k}\leq 2^n$

Show that ${n\choose k}\leq 2^n$ for all naturals with $0\leq k \leq n $.I know I need to use induction and for the base case $n=1$ what exactly am I showing?
-1
votes
3answers
63 views

Prove the inequality by induction [duplicate]

Prove the inequality by induction: $3^n > n^3\ $ for $\ n \geq 4$ Edit: 1) Base case: $n=4$, $3^4>4^3, 81>64$ 2) Assume true for n=k: so $3^k>k^3$ 3) Consider $(k+1)^3$, $(k+1)^3 = ...
0
votes
1answer
55 views

strong induction case

im stuck on this assignment. Can someone give me a hint? Here is the assignment: There are two types of creature on planet Char, Z-lings and B-lings. Furthermore, every creature belongs to a ...
0
votes
1answer
23 views

Proof by induction with the Union of sets

Proof by induction: $$ P( \cup _{i=1}^n A_i)=\sum_{i=1}^n P(A_i) - \sum_{1 \leq i_1 < i_2 \leq n} P(A_{i_1} \cap A _{i2} ) + \sum_{1 \leq i_1 < i_2 <i_3 \leq n} P(A_{i1} \cap A_{i2} \cap ...
1
vote
3answers
61 views

Mathematical Induction getting the right side

So I 've been doing Mathematical Inductions but I seem to have a issue in simplify and getting the right side. So I have this on the L.H.S $$\frac{k(k + 1)(2k +1)}{6} + (k + 1)^2 $$ And I'm trying ...
0
votes
1answer
36 views

Prove that $\sum_{k=1}^{n-1}k^{3}\leq \frac{n^{4}}{4}\leq \sum_{k=1}^{n}k^{3}$ for all $n\geq 2$.

Prove that $$\sum_{k=1}^{n-1}k^{3}\leq \frac{n^{4}}{4}\leq \sum_{k=1}^{n}k^{3}$$ for all $n\geq 2$. This is just a random exercise to improve my proof techniques. I want to show it by induction ...
4
votes
3answers
81 views

Proof of $\sum^{2N}_{n=1} \frac{(-1)^{n-1}}{n} = \sum^{N}_{n=1} \frac{1}{N+n}$

The title pretty much summarizes my question. I am trying to prove the following: $$\displaystyle \forall N \in \mathbb{N}: \sum^{2N}_{n=1} \frac{(-1)^{n-1}}{n} = \sum^{N}_{n=1} \frac{1}{N+n}.$$ I ...
4
votes
3answers
60 views

Show that $\frac{1\cdot 3\cdot 5\cdot \ldots \cdot (2n-1)}{1\cdot 2\cdot 3\cdot \ldots \cdot n}\leq 2^{n}$ for all $n\in\mathbb{N}$.

Show that $$\frac{1\cdot 3\cdot 5\cdot \ldots \cdot (2n-1)}{1\cdot 2\cdot 3\cdot \ldots \cdot n}\leq 2^{n}\qquad (n\in \mathbb{N}).$$ I want to show the last step, that is, the inductive step. ...
3
votes
0answers
27 views

Real Induction Over Multiple Variables?

I've seen in multiple places that one can use normal mathematical induction to prove the truth of a statement that relies not on just one variable (say, $x$,) but multiple variables (for example, $a$, ...
4
votes
3answers
59 views

Induction proofs for subsets of integers

I know that induction can be used to prove that certain results hold true for all integers, all positive integers, all negative integers, all rational numbers and so on. What I'm noticing from listing ...
2
votes
2answers
35 views

Proofs: Induction on Handsakes

Here is the problem: Suppose $n$ people are at a party, and some number of them shake hands. At the end of the party, each guest $G_i$, $1 \leq i \leq n$ shares that they shook hands $x_i$ times. ...
0
votes
0answers
53 views

Transition matrix proof

Let $P=\begin{bmatrix}1-a&a\\b&1-b\end{bmatrix}$, with $0<a,b<1$. Show that ...
0
votes
0answers
44 views

How do I solve Exercise 6.2.4 (a) of 'How to Prove It' by Velleman?

I spent 6 hours on it, and I couldn't wrap my head around it. The problem is described below. I am stuck on Case 2. 6.2.4. (a) Suppose R is a relation on A, and ∀x∈A∀y∈A(xRy ∨ yRx). (Note that this ...
0
votes
3answers
65 views

Prove the laws of exponents by induction

We inductively define $a^1=a, a^{n+1}=a^n a$. I want to show that $a^{n+m}=a^n a^m$. By definition, this is true if $m=1$. Now for $m=2$, we have $$ \begin{align} a^{n+2} =& a^{(n+1)+1}\\ ...
-1
votes
1answer
82 views

Strong induction different assumptions

I have a question regarding strong induction. I've seen examples on proofs that assume that P(n) is true for all n that is smaller or equal than k and thereby dealing with k+1 in the inductive step ...
0
votes
3answers
36 views

Given two specific sets, show that one is a subset of another

Given $$X = \{x : x = 4^n-3n-1 ; n\in\mathbb{N}\}$$ and $$Y = \{y : y = 9(n-1); n\in\mathbb{N}\}$$ Prove that $X \subset Y$. I've been struggling with this problem for hours but I couldn't find a ...
1
vote
1answer
44 views

Proving property of group-like algebraic structures by means of induction

How do you prove (by means of induction) that the following is true for all group-like algebraic structures? $$\operatorname{ord}(a_1 \circ a_2 \circ a_3 \circ \cdots \circ a_{n-1} \circ a_n) = ...
1
vote
0answers
26 views

The pencils in a box of crayons always have the same color [duplicate]

I retrieved an old math book and I'm delighted to share following exercise. The pencils in a box of crayons always have the same color. Proof by induction on the number $n$ of pencils in the ...
1
vote
1answer
20 views

More detailed explanation of how $2N_{h-2}$ becomes $2^{h/2}$?

I'm trying to learn the proof of the minimum number of nodes in an AVL tree of height h and I'm stumped on how $2N_{h-2}$ becomes $2^{h/2}$. I've read this [answer](How does $2N_{h-2}$ become ...
1
vote
2answers
33 views

Prove that $\tan \left ( \sum_{k=1}^{n} \theta_k \right ) \geq \sum_{k=1}^{n} \tan (\theta_k)$

I'm trying to prove by induction that $$\tan \left ( \sum_{k=1}^{n} \theta_k \right ) \geq \sum_{k=1}^{n} \tan (\theta_k)$$ provided that $$\sum_{k=1}^{n} \theta_k < \frac{\pi}{2}$$ So in ...
3
votes
3answers
66 views

Basic mathematical induction regarding inequalities

These are just the examples from my textbook, but I don't think it did not explain well. One of the problem was to prove the inequality $$n<2^n$$ for all integers $n$. I understand we assume ...
0
votes
2answers
43 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
42 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 ...
2
votes
2answers
68 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 ...
3
votes
1answer
43 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
1answer
54 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} = ...
1
vote
1answer
33 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 ...
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 ) ...
1
vote
2answers
33 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 ...
9
votes
6answers
393 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 ...
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) ...
7
votes
3answers
431 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 ...
1
vote
0answers
46 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 ...
2
votes
1answer
14 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$ ...
1
vote
1answer
22 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 ...
7
votes
2answers
85 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 ...
0
votes
3answers
44 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 ...
-1
votes
3answers
33 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 ...
0
votes
0answers
36 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$ ...
0
votes
1answer
85 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 ...
0
votes
2answers
76 views

Prove by induction $\sum\limits_{k=m}^{\ n}{n\choose k}{k\choose m}={n\choose m}2^{n-m}$

I can't figure out what is the base case. Could someone show the steps?
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
41 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
83 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
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 ...
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, ...