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
36 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
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 ...
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
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} = ...
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
362 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
423 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
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 ...
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 [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 ...
-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
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. ...
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 ...
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: ...
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 ...
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
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
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 ...
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
35 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
44 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: $ ...
1
vote
0answers
24 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
68 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
62 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 ...
-1
votes
0answers
23 views

mathematical induction, addition squares [duplicate]

I am trying to solve following problem: 1^2 + 2^2 + 3^2 + ... + n^2=(n(n+1)(2n+1))/6 please write complete solution in detail. I viewed some solutions but I am lost. Thank you very much in advance. ...
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 ...
0
votes
0answers
9 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
72 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' ...