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

Strong induction MIT [on hold]

Can someone help me solve assignment 5 using the strong induction method? ...
0
votes
3answers
30 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
26 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
25 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
18 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 ...
0
votes
3answers
77 views

Inductive proof for familiar exponent rule $a^n\cdot b^n = (ab)^n$ [on hold]

Using an inductive proof for all integers $n \geq 1$, prove that $a^n \cdot b^n = (ab)^n$. Can't use only algebra and the commutative law.
3
votes
3answers
62 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
38 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 ...
2
votes
2answers
61 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 ...
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
1answer
46 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
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 ...
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 ...
9
votes
6answers
369 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) ...
6
votes
3answers
424 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 ...
-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
41 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
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$ ...
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 [closed]

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 ...
-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 ...
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$ ...
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 ...
0
votes
2answers
71 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
108 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
39 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
119 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
78 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 ...
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, ...
2
votes
3answers
83 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
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
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
81 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
42 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
39 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
70 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
38 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
45 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
28 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
66 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: $ ...