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

8
votes
1answer
59 views

Is there a standard name for this “continuous induction” principle?

I am working on a paper, and I want to prove that some statement $P(x)$ holds for every value of a parameter $x \in [0,\infty)$. I plan to proceed as follows: Show that $P(0)$; Show that if $P(x)$ ...
3
votes
6answers
85 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
0answers
71 views

Why is $y + 1$ infinite?

This is related to SO question : http://stackoverflow.com/questions/30150877/why-does-this-cause-ghci-to-hang but I'm having difficulty understanding why Haskell enters an infinite loop but since ...
3
votes
8answers
116 views

Proving that $12^n + 2(5^{n-1})$ is a multiple of 7 for $n\geq 1$ by induction

Prove by induction that $12^n + 2(5^{n-1})$ is a multiple of $7$. Here's where I am right now: Assume $n= k $ is correct: $$12^k+2(5^{k-1}) = 7k.$$ Let $n= k+1 $: $$12^{k+1} + 2(5^k)$$ ...
3
votes
2answers
45 views

simplifying equations

I have been trying to study analysis of algorithms with mathematical induction yet I found my algebra skills are very poor. So now I began restuddiing algebra (factoring, destributive property, ...
3
votes
3answers
53 views

Prove that Euclid's algorithm computes the GCD of any pair of nonnegative integers

I've been struggling with a basic exercise involving Euclid's algorithm and mathematical induction. Given the following definition of the Euclid's algorithm (in Java): ...
1
vote
1answer
34 views

How to show $(1+a)^n<1+2^n a$ for all $n\in\mathbb N$ and $a\in (0, 1)$?

There is an induction problem which is baffling me. I'm supposed to use induction to show the inequality $$(1+a)^n< 1+2^n a,$$ for all $n\in\mathbb N$ and $a\in (0, 1)$. I guess there must be some ...
0
votes
1answer
57 views

Show that there exists a unique function with a certain property

I'm trying to prove the following theorem: "Let $~f: \mathbb{N} \times \mathbb{N} \to \mathbb{N}~$ be a function, and let $~c~$ be a natural number. Show that there exists a unique function $~a: ...
0
votes
2answers
33 views

Using induction prove $\sum\limits_{k=1}^n\dbinom{k}{k-1}$=$\binom{n+1}{n-1}$

$\sum\limits_{k=1}^n\dbinom{k}{k-1}$=$\binom{n+1}{n-1}$ We are supposed to use induction to prove this inequality. After the base case, I tried to use the definition $\binom{n}{k} = ...
8
votes
6answers
267 views

Proof without using induction [duplicate]

How to prove that $$1^2+2^2+...+n^2=\frac{n(n+1)(2n+1)}{6}$$ without using induction. If we don't know the right side of this expression, how to get right expression. I tried with partial sums and ...
2
votes
1answer
61 views

how to prove by induction the $ (1+x)^{n}>1+nx+nx^2$

Prove by induction the formula $ (1+x)^{n}>1+nx+nx^2$ for $x>0$ real number and $n\ge 3$ my try : multiply both sides by $(1+x)$ gives $ (1+x)^{n+1}>1+(n+1)x+(2n+nx)x^2$ have I done ...
1
vote
2answers
70 views

Prove that if $\sum \limits_{k=1}^{n} x_n=1$ then $\sum \limits_{k=1}^{n} x_n^2 \geq {1 \over n}$

Prove that if $\sum \limits_{k=1}^{n} x_n=1$ then $\sum \limits_{k=1}^{n} x_n^2 \geq {1 \over n}$ where $\{x_k\}_1^n$ are real numbers which are not all the same. I tried to prove it by induction. ...
1
vote
2answers
31 views

Is this inductive big O proof possible / Does this question make sense?

Prove that $\sum_{i=j}^k \frac 1i$ is $O(\ln(k)-\ln(j-1))$ using induction for all $i$. The way I understand this question, it's nonsense - $i$ is the iteration variable, not something that can be ...
0
votes
1answer
32 views

How to prove this by induction

Prove by induction the following equality : $\ 1-4+9-16+\cdots+(-1)^{n+1} n^2 = (-1)^{n+1}(1+2+3+\cdots+n) $ I don't know what to do in this case, I know what to do in general but can do this one
1
vote
3answers
38 views

Question regarding proving by induction

I am struggling with a math problem I have been assigned. The problem is as follows: Let $X_1 = -3$ and $X_2 = 0$. Given that for every natural number $n \geq 2, X_{n+1} = 7X_n - 10X_{n-1}$, prove by ...
5
votes
1answer
62 views

Partition onto subsets at the same sum

Positive integers $ a_1, a_2,\ldots, a_n $ such that $ a_k\leq k $ and the sum of all these numbers is even and equal to $ 2S $. Prove that the number can be divided into two groups, the amount of ...
0
votes
2answers
69 views

Using induction to prove letter arrangement

There are n letters written to different people, and envelopes correspondingly addressed. The letters are mixed before being sealed in envelops, the effect being to make n!allocations of letters to ...
4
votes
8answers
159 views

Proving that $5^n-1$ is divisible by $4$ for $n\geq 0$ by induction

I hope this is not counted as a duplicate, as I would like to know if my proof is valid: $P(n): 5^n - 1$ is divisible by $4$ for $n \ge 0$. Base Step: $P(0): 5^0-1 = 1-1 = 0 = 0\times 4$. Induction ...
-1
votes
2answers
77 views

What are the prerequisites required if I have to do induction to prove a certain theorem

I have always been fascinated by mathematical induction. The idea of induction is itself such a great analogy. But sometimes induction makes me feel that it is very messy. My professor keeps on saying ...
0
votes
4answers
44 views

Show that the sequence is monotone and bounded.

Show that the sequence defined by $a_1=1$ and $a_n=\sqrt{3+a_{n-1}}$ for $n>1$ is monotone and bounded. Then find the limit of the sequence. I'm supposed to do this using induction. I'm usually ...
1
vote
3answers
67 views

How to prove a Fibonacci inequality using Strong Induction?

Using strong induction I am trying to prove that $$F_n \geq \left(\frac{1+\sqrt{5}}{2}\right)^{n-2} \text{ for all } n \geq 2$$ for the Fibonacci Sequence defined by: $F_0 = 0$, $F_1 = 1$, and $F_n ...
1
vote
1answer
37 views

Induction Clarification

I had this problem: Is it always necessary to go from n to (n + 1) or from (n - 1) to n in the inductive hypothesis? Is the "direction" always important? Here is my solution to one such proof, which ...
1
vote
2answers
61 views

How to prove that the statement $ 4+10+16 + \cdots + (6n-2) = n(3n+1)$ for all $n \ge 1$ using mathematical induction?

I know you begin by establishing that it is true for $n=1$ which gives $6(1)-2 = 1(3\cdot1\cdot+1)$. Then I replace each $n$ for a $k$, and I suppose that is true for $6k-2=k(3k+1)$. But then the ...
2
votes
0answers
58 views

Properties of Ackermann's function

I want to show the following properties of Ackermann's function: $A(x,y)>y$. $A(x,y+1)>A(x,y)$. If $y_2>y_1$, then $A(x,y_2)>A(x,y_1)$. $A(x+1, y) \geq A(x,y+1)$. $A(x,y)>x$. If ...
3
votes
2answers
75 views

Solve the following recurrence relation: $S(1) = 2$; $S(n) = 2S(n-1)+n2^n, n \ge 2$

Solve the following recurrence relation: $$\begin{align} S(1) &= 2 \\ S(n) &= 2S(n-1) + n 2^n, n \ge 2 \end{align}$$ I tried expanding the relation, but could not figure out what the closed ...
1
vote
2answers
70 views

Proving $n^2≤2^n+1$ for $n\geq 1$ by induction

Prove $n^2\leq 2^n+1$ for $n\geq 1$ using induction. Proof. For $n=1, (1)^2\leq 2^1+1=3$. $\therefore 1\leq 3$ is true. Assume $n=k$ is true so $k^2\leq 2^k+1$ or $k^2-1\leq 2^k$. Then prove for ...
4
votes
5answers
145 views

Inequality in Algebra: $1 \leq x_1 x_2 \cdots x_n$ implies that $2^{n} \leq (1 + x_1)(1+x_2) \cdots (1 + x_n).$

How do I prove that if $x_1, \ldots, x_n$ are positive real numbers, then $$1 \leq x_1 x_2 \cdots x_n \text{ implies that } 2^{n} \leq (1 + x_1)(1+x_2) \cdots (1 + x_n).$$ I attempted a proof by ...
1
vote
2answers
71 views

Confusion about how to prove $\sum_{i=0}^n 2^i = 2^{n+1}-1$ for all $n\geq 0$ by induction

I'm trying to understanding proof by induction. But how do I check if that is correct? How do I know what I need to show? Any help would be great. Just trying to get my head around this. So I have ...
0
votes
2answers
45 views

Strong Induction

Define a recursive sequence $a_0$, $a_1$, $a_2$, . . . by $a_0 =1$,$a_1 =3$, $a_n$ = $2a_{n−1}$ + $8a_{n−2}$ for all integers $n≥2$ Prove by strong induction that $a_n$ $≤ 4^n$ for all integers $n ≥ ...
1
vote
3answers
83 views

Show that the sequence defined recursively by $a_{n+1} = \sqrt{3a_n + 1}$ is increasing

Assume that the sequence ${a_n}$ is defined recursively by $a_{n+1} = \sqrt{3a_n + 1}$ for all $n \in \mathbb N$, with $a_1 = 1$. Use mathematical induction to prove that $a_n \leq a_{n+1}$ for all ...
1
vote
1answer
36 views

Proving Inequality using Induction.

I am trying to prove the following statement: For every nonnegative integer $n$, $1+6n \le 7^n$. I did the base case where $n=0$ but am having trouble manipulating the inductive step. So far I ...
1
vote
2answers
29 views

How do I prove this with induction?

I am give $a_{n+1}=\sqrt{a_{n}+12}$ and $a_{n}∈[-12, 4]$. I need to prove $0≤a_{n}≤4$ for all $n≥2$. I have that $a_{2}∈[0,4]$ so it works for the first case and $a_{3}∈[\sqrt{12},4]$ so it holds for ...
0
votes
0answers
40 views

Solving a general system of linear equations

We are given a system with n linear equation: $$\forall i\in \{1,...,n\}: i \cdot x_i + \sum_{j=i+1}^{n}x_j= \frac{i}{n}$$ Prove that the solution for this system of equation is $$\forall i\in ...
2
votes
1answer
32 views

Understanding an application of induction in a proof

I understand what is done below, however I don't understand the induction used, especially not when applying $0\leq n$. If $s_n+1=f(s_n)$ with $|f′(x)|\leq 1/2$ prove that the sequence $s_n$ ...
-1
votes
3answers
100 views

Use mathematical induction to prove a statement [closed]

Use mathematical induction to prove that: $$A\cap\left(\bigcup_{i=1}^nB_i\right) = \bigcup_{i=1}^n\left(A\cap B_i\right)$$
0
votes
2answers
26 views

Help with solving mathematical induction problem

I need help with the following: Use mathematical induction to prove that for every $n\in N$, $$ \sum_{k=1}^n\frac{1}{\cos kx \cos(k+1)x}=\frac{\tan(n+1)x-\tan x}{\sin x} $$ For $n=1$, the statement ...
0
votes
2answers
73 views

Prove for integers $a,b\ge 3$ that $a^2+b^2+1>(a+1)(b+1)$

Prove for integers $a,b\ge 3$ that $a^2+b^2+1>(a+1)(b+1)$. Original question asked for positive real solutions, but I've changed it to integers. It's question I've come up with. AM-GM ...
2
votes
3answers
55 views

Can mathematical inductions work for other sets?

I know that induction works only for the natural numbers $\mathbb{N}$. We first have to prove the base case. And we then prove that if the statement $p(k)$ holds then $\color{blue}{\textbf{p(k+1)}}$ ...
0
votes
2answers
57 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.
3
votes
2answers
52 views

Proof By Contradiction [?]

There are $n$ islands with $n$ bridges connecting pairs of islands (where $n\ge 2$). Prove that some sequence of distinct bridges forms a loop. __ Since it isn't obvious how to prove it directly I ...
2
votes
3answers
202 views

How to prove a sum of series

How do I prove that for any natural number $n$ we have $$\sum_{i=0}^n i^4 \neq \left(\sum_{i=0}^n i\right)^3?$$ Any help would be greatly appreciated.
0
votes
1answer
29 views

Help with a demonstration with triangle numbers

Recently I've been doing some work with trianglular numbers. Basically I wanted to show that for every nth triangular number $T_n$ $$T_n=\frac{n(n+1)}2$$ For me the simplicity if this equation is ...
6
votes
4answers
111 views

Inductive Proof that $k!<k^k$, for $k\geq 2$.

Call $P(k): k!<k^k$, for $k\geq 2$ Test it out with 2, and it's true ($2<4$). Assume that $P(k)$ is true for some $k\geq2$. Then show that $P(k+1)$ is true. $P(k+1): (k+1)!<(k+1)^{k+1}$ ...
2
votes
2answers
36 views

Help with Factorial Inequality Induction proof

So I'm asked to prove $3^n + n! \le (n+3)!$, $\forall \ n \in \mathbb N$ by induction. However I'm getting stuck in the induction step. What I have is: (n=1) $3^{(1)} + (1)! = 4$ and $((1) + 3)! = ...
3
votes
3answers
116 views

Proof verification for proving $\forall n \ge 2, 1 + \frac1{2^2} + \frac1{3^2} + \cdots + \frac1{n^2} < 2 − \frac1n$ by induction

Prove by mathematical induction: $\forall n \ge 2, 1 + \frac1{2^2} + \frac1{3^2} + \cdots + \frac1{n^2} < 2 − \frac1n$ Basis Step: (We want to show, $P(2)$, which is 1 + ...
1
vote
3answers
47 views

Simple Induction Proof

How would one go about proving that $$0<\frac{n}{n+1}<1$$ by mathematical induction? If $p(n)$ is the statement as above, then I know we show $p(1)$, and assume $p(n)$, but in this particular ...
2
votes
1answer
50 views

Induction Proof on String

Formally prove the correctness of the union construction as follows. Let $M_1$ and $M_2$ be the two $\lambda$-NFA's constructed for $R_1$ and $R_2$ and let $N$ be the $\lambda$-NFA constructed so ...
2
votes
1answer
49 views

Proving the principle of definition by generalized recursion using the inductive closure of an induction system

I'm working through Hinman's Fundamentals of Mathematical Logic in order to review some things, and got stuck in an exercise from section 1.2. Specifically, he asks us to prove (what he calls) the ...
5
votes
1answer
69 views

Proving $\frac {2n}{(a+b)^n} \le \frac {1}{a^n} + \frac {1}{b^n}$ for $a,b>0, n\in\mathbb{N}$ by induction

prove using induction: $$ \frac {2n}{(a+b)^n} \le \frac {1}{a^n} + \frac {1}{b^n} $$ $$a,b \gt 0 , n \in N$$ my attempt: base $n=1$: $$ \frac {2}{(a+b)} \le \frac {1}{a} + \frac {1}{b}$$ ...
3
votes
3answers
42 views

Proving that $8^n-2^n$ is a multiple of $6$ for all $n\geq 0$ by induction

I have the following induction problem: $8^n-2^n$ is a multiple of $6$ for all integers $n\geq 0$. So far this is what I've done: Base case: $n = 0$ $8^0-2^0 = 6$ $1 - 1 = 6$ $0 = 6$ This ...