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

1
vote
1answer
65 views

Product matrix and induction

I am not sure which method to use here. Should I do it for $n=2$ and $n=3$ and then use induction on $n$? Let $\alpha_1,\alpha_2,\ldots,\alpha_n \in \mathbb{R}$, where $n \geq 2$. Show that ...
0
votes
1answer
49 views

Is this Proof by Induction a backwards proof?

let $P(n)$ be the statement that $1*1!+2*2!+...+n*n! = (n+1)! -1$ P(1) is true because $1*1! = (1+1)! - 1 = 1$ Assume $P(n)$. Shall show that $P(n+1)$ holds. $1*1!+2*2!+...+n*n! + (n+1)(n+1)! = ...
1
vote
1answer
27 views

Duplicate - Proof by Ordinary Induction: $a^n-b^n \leq na^{n-1}(a-b)$

This question has already been asked: Proving Inequality using Induction $a^n-b^n \leq na^{n-1}(a-b)$ However has not been answered properly. (Even thought the OP checked an answer) The answers ...
-1
votes
1answer
65 views

Given the definition of $\leq$, prove $((a \leq b) \implies (b \leq a)) \implies (a = b)$.

Given the definition of $\leq$, prove $((a \leq b) \implies (b \leq a)) \implies (a = b)$. $\leq$ is defined as: $a \leq$ b := Case $a=0: True$ Case $a=Succ(p)$: ....Case $b=0: False$ ....Case ...
2
votes
6answers
90 views

Prove that $n(n+1)(n+5)$ is a multiple of $6$

I need to prove that $n(n+1)(n+5)$ is divisible by 6. where $n$ is a natural number. I have used the method of induction. But not successful I got the expression $(k^3+6k^2+5k)+3k^2+15k+12$ when ...
3
votes
5answers
76 views

Proof by induction: Show that $9^n-2^n$ for any $n$ natural number is divisible by $7$.

Can someone please solve following problem. Show that $9^n-2^n$ for any $n$ natural number is divisible by $7$. ($9 ^ n$ = $9$ to the power of $n$). I know the principle of induction but am stuck ...
3
votes
2answers
58 views

Difference operator: Proof by induction that $\Delta^k (X_t)= k!a_k+\Delta^k (Y_t)$

Hello I am having issues with the following exercise. I have to prove that $$\Delta^k (X_t)= k!a_k+\Delta^k (Y_t)$$ where $X_t = m_t +Y_t=\sum_{j=0}^ka_jt^j+Y_t$ for $t \in \mathbb {Z}$. Note: ...
0
votes
1answer
45 views

Prove by mathematical induction, or otherwise, that for all integers $n\ge 1$ [duplicate]

$$\cos(1)+\cos(2)+\ldots+\cos(n-1)= \cos(n)-\cos(n-1)/(2\cos(1)-2 ) -1/2$$ Here is my attempt: Let $P(n)$ be this statement. $P(1)$ is true since $0=\cos(1)-\cos(1-1)/(2\cos(1)-2) -1/2$ Suppose ...
0
votes
0answers
43 views

proof by induction that $\sum_{k = n}^{m} \binom{k}{n} = \binom{m + 1}{n + 1}$ [duplicate]

I am unable to solve following proof by induction. $$\sum_{k = n}^{m} \binom{k}{n} = \binom{m + 1}{n + 1}$$ Can you please help me ? a) show that it is true for $n=m$ b) show that it is true for ...
1
vote
2answers
53 views

Prove ${n \choose k} = {n \choose k-1}\frac{n-k+1}{k}$

I am looking to prove, by induction, the following equality:$${n \choose k} = {n \choose k-1}\frac{n-k+1}{k}$$ From Pascal's identity, I know we have that $${n+1 \choose k} = {n \choose k} + {n ...
0
votes
5answers
58 views

I'm having trouble with a proof by induction

This one should be pretty easy as its only a first year math problem. it s proof by induction that Im having trouble with. $$let\;x_{1}=1; for\;each\;n\in \mathbb{N}\;let\;x_{n+1}=\frac{2}{3}x_{n}+1; ...
-1
votes
2answers
51 views

Use strong induction to prove the ones digit of 4^k.

The question is to prove the following using strong induction: "For 4^k, where k is a nonnegative integer, if k is even then the ones digit of 4^k is 6 and if k is odd then the ones digit of 4^k is ...
1
vote
1answer
25 views

Show a sequence converges, and determine its limit

I have a sequence $\langle x_{n}\rangle$ is defined by $x_1 = h$ and $x_{n+1} = x^2_n+k$ where $0<k<1/4$ and $h$ lies between the roots $a$ and $b$ of the equation $x^2-x+k = 0$ (1) ...
2
votes
0answers
30 views

Pascal's triangle induction proof

I am trying to prove $$\binom{n}{k} = \binom{n}{k-1}\frac{n-k+1}{k}$$ for each $k \in \{1,...,n\}$ by induction. My professor gave us a hint for the inductive step to use the following four ...
0
votes
1answer
60 views

Prove the following equality: $ \sum_{i=0} ^n j {n \choose j} = n 2^{n-1} $ [duplicate]

I'd like some help. My first idea was to use induction, but then I get stuck. The base case works just fine, as you'd imagine, and then... If $ \sum_{i=0} ^n j {n \choose j} = n 2^{n-1} \rightarrow ...
2
votes
1answer
53 views

For all graphs $\alpha(G) \ge \sum\limits_{x \ V(G)} \frac{1}{deg(x) + 1}$

Prove for all graphs $\alpha(G) \ge \displaystyle \sum_{x \ V(G)} \frac{1}{deg(x) + 1}$ $\alpha(G) :=$ maximum independent set. I think induction is the best way to do this but I'm not sure what I ...
0
votes
2answers
22 views

Proving correctness of a recursive function of multiplication by induction.

Define multiplication of two numbers y and z as: $$m_c(y,z)=\begin{cases}0&z=0\\m_c\left(cy,\left\lfloor \frac zc\right\rfloor\right)+y(z\mod c)&z\neq 0\end{cases}\tag{$\forall c\geq 2$}$$ Now ...
2
votes
2answers
62 views

Prove that for all $n \geq 1$, $F_{-n}$ = $(-1)^{n+1}F_n$ where F is the Fibonacci numbers.

Prove that for all $n \geq 1$, $F_{-n}$ = $(-1)^{n+1}F_n$ where F is the Fibonacci numbers. I've already shown that the formula holds for $n = 1$ and $n = 2$. So I supposed the formula holds for $n$ ...
0
votes
1answer
29 views

Understanding AGM Induction

Without loss of generality, assume that $a_n$ is the largest number among all the $a_i$'s. Let's denote the arithmetic and geometric means of the first $n-1$ numbers by $A$ and $G$, respectively ...
0
votes
1answer
25 views

Confused about a simplification step in induction

Hello - I don't know how they got from the 3rd line to the 4th line. I understand all other parts of the simplification.
4
votes
4answers
64 views

Prove by induction that $n^2 < 2^n$ for all $n \geq 5$?

So far I have this: First consider $n = 5$. In this case $(5)^2 < 2^5$, or $25 < 32$. So the inequality holds for $n = 5$. Next, suppose that $n^2 < 2^n$ and $n \geq 5$. Now I have to prove ...
5
votes
4answers
533 views

What's the benefit of using strong induction when it's replaceable by weak induction?

Example of a proof of a theorem using weak(ordinary) induction The two types of inductions have process of proving P(a) and "for all integers $n \ge b, P(n)$" as a result in common. For example, ...
0
votes
1answer
25 views

How to use the induction steps on these?

So I have this problem I don`t quite know how to prove completely with $P(k)>P(k+1)$ implication: $x$ is a real number with the property that $x + \frac1x$ is an integer, then prove that $x^n + ...
1
vote
1answer
23 views

Round robin with $2^n$ teams.

Show that if there are $2^n$ teams in a round robin tournament, and every team plays against each other team exactly once, we can find n+1 teams who can be listed in a column such that each team in ...
0
votes
0answers
23 views

Proving equation in Eulers transformation for series

Euler's transformation for series is here defined: Equation (5) http://mathworld.wolfram.com/EulersSeriesTransformation.html In Equation (9), (10) and (11) they shows how this definition is ...
0
votes
0answers
21 views

Induction on $t_k$

I need to show by induction that: $$t_k=kt_1-4\binom k2$$ I know that $t_1=\frac 14+\frac 12 (t_1+1)+\frac 14 (t_2+1)$, $t_2=2t_1-4$, $t_k=\frac 14((t_{k-1}+1)+2(t_k+1)+(t_{k+1}+1))$ and ...
0
votes
1answer
32 views

Proving that any two consecutive elements of codomain of a function are relatively prime

$h$ is defined as follows: $ h(1) = h(2) = 1; h(n) = (h(n-1))^2 + h(n-2)$ if $n > 2$. Prove that for all n>1 that the $gcd(h(n), h(n-1)) = 1$. My attempt with proof by induction: Let $P(n)$ be ...
1
vote
1answer
45 views

Having trouble with an Inductive proof

Define On as inductively as follows: O1 = {1}; On+1 = On ∪ {2n+1}. Let O = ∪nOn. Let O = ∪nOn Prove by Induction that On = {1,3,...,2n-1} P(n) would be the statement that On+1 = On ∪ {2n+1}. ...
1
vote
1answer
26 views

Induction on a sequence {$a_n$}

Let a sequence be defined by $a_0=1$ and $a_{n+1}=\sqrt{3a_n+4}$. Prove by inductions that $0\le a_n \le 4$ for all n. For some reason I can't figure out what my hypothesis is? I know my base case is ...
0
votes
0answers
35 views

Proof of Replaceability of Equivalent Formulas by Structural Induction

My class discussed the following theorem for which I wasn't able to make it to class. Its proof is supposed to involve structural induction but I am stuck in the inductive step... Let B |=| C. If A' ...
0
votes
2answers
35 views

Proving that either of the two numbers are greater or equal to their arithmetic mean.

The arithmetic mean of two numbers $x$ and $y$ is $k$. Show that either $x \ge k$ or $y \ge k$. Can anyone explain what approach should I use?
-2
votes
4answers
44 views

Fibonacci Numbers Induction?

Show that $a_n=n^2+n+1$ satisfies \begin{cases} a_0=1\\ a_k=a_{k-1}+2k & \text{for $k>0$} \end{cases} I want to use induction to solve this problem. but I don't know what my base will be ...
2
votes
3answers
31 views

Mathematical induction on a finite subset of $\mathbb{N}$

I'm trying to prove the following using induction (or well-ordering principle). (Induction says that whenever $ 0 \in S $ and $ n \in S \implies (n+1) \in S$, then $S = \mathbb{N} $. ) Let $ \{ P_{k} ...
2
votes
1answer
38 views

Prove Lucas numbers and Fibonacci numbers relation $F_n = \frac{L_{n - 1} + L_{n + 1}}{5}$

$F_n$, is the $n$th term of the Fibonacci sequence. $L_n$ is the $n$th Lucas number. I want to prove that $F_n = \dfrac{L_{n-1}+L_{n+1}}5 $. Things I know: $L_n$+$L_{n+1}=L_{n+2}$ $F_{n-1} + ...
0
votes
1answer
26 views

Constructive induction to find a formula for a summation

I am looking to find the values of a b and c for an equation of this summation, but am getting lost on how to solve it. $$\sum_{i=1}^n 12^i = an2^n + b2^n + c$$ $$\sum_{i=1}^{n+1} 12^i = \sum_{i=1}^n ...
3
votes
6answers
135 views

Proof that the sum of the first $n$ odd numbers is $n^2$.

Here is what I have so far: The $n$th odd number is $2n-1$. So we prove that $1+3+...+(2n-3)+(2n-1)= n^2$. Separate the last term and you get: $[1+3+...+(2n-3)]+(2n-1)$ $[1+3+...+(2n-3)]$ is the ...
2
votes
0answers
43 views

Proof by induction with polynomials

I need to prove by induction the following equality. I did the inductive hypothesis part, but I don't get it when $n=1$. Any help/ hints are greatly appreciated. Be $x\neq 1$ and a real number, prove ...
1
vote
1answer
43 views

Induction Example

Here's a (possibly sloppily written) Induction proof that has me stumped. It's the first example from here and supposedly the statement holds? ...
2
votes
1answer
30 views

Similar matrix proof problem

So the question asks: Give a full proof, by mathematical induction, that if the two n × n matrices A and B are similar, then so are $A^n$ and $B^n$, for every $n ∈ N.$ So so far I have: Base case: ...
0
votes
3answers
82 views

Prove by induction that $a_{n+1} = a_{n} + a_{n}$

I flip a fair coin $n$ times, the amount of possible outcomes is $2^n$. I'm trying to prove that the number of possible combinations that result in an even amount of heads after $n+1$ flips is equal ...
0
votes
1answer
29 views

Induction and Recursion Proof using Catalan Numbers

Note that a product may be parenthesized in two different ways: and . Similarly, there are several different ways to parenthesize . Two such ways are and . Let be the number of different ways to ...
3
votes
1answer
36 views

Triangular Inequality using Induction

The triangle inequality for absolute value that for all real numbers a and b, Use the recursive definition of summation, the triangle inequality, the definition of absolute value, and mathematical ...
0
votes
1answer
27 views

Using the Fibonacci sequence and deduction to prove… [duplicate]

Using the Fibonacci sequence and induction prove that $$F_{n-1}F_{n+1}-F_{n}^2 = (-1)^n, \space \space n=1,2,3...$$ My efforts so far: The basis holds for $n=1$ Induction step: ...
32
votes
3answers
3k views

Can't find the flaw in the reasoning for this proof by induction?

I was looking over this problem and I'm not sure what's wrong with this proof by induction. Here is the question: Find the flaw in this induction proof. Claim $3n=0$ for all $n\ge 0$. ...
1
vote
2answers
48 views

How to proceed with induction step of induction proof

$$ P(n): (1+a)^n \geq 1 + a(n - 1) \\ a \geq 0 $$ I already proved its base case with n = 1, which is pretty simple. However, I am confused on how to proceed with my induction step of $$ P(n+1): ...
1
vote
1answer
24 views

Induction with summation. How to factor out

Hey Everyone, So here is the problem I am currently working on and I have a few questions with what I can factor our of the sigma notation in order to use the IH. Base Case: $1$ is the base case ...
3
votes
2answers
42 views

Prove by induction that: $\sum^{2n}_{i=1} \frac{(-1)^{i-1}}{i}=\sum^n_{i=1}\frac{1}{n+i}$

Basis step: For $n=1$, equation holds. Inductive step: Now, $$\sum^{2n}_{i=1} \frac{(-1)^{i-1}}{i}=\sum^n_{i=1}\frac{1}{n+i} \tag{i. h.}$$ Now we want to show that $$\sum^{2n+2}_{i=1} ...
2
votes
0answers
30 views

Induction on Binary Trees

I am trying to show that $\sum_{i=1}^{M} 2^{-di} \leq 1 $ for a Binary Tree with $M$ leaves each with a depth of $d_i$. I understand intuitively why this is the case, as every subtree at level d, ...
3
votes
0answers
33 views

Complete Graphs as Unions of Paths

Show that for $n \geq 2$ the complete graph $K_n$ is the union of paths of distinct lengths. I have been stuck on this problem for the past couple of days now and would really like to see a ...