0
votes
1answer
41 views

Induction proof that $4^n > 3^n+2^n$ for $n\ge2$

This is a problem with induction and proofs but I'm not sure how to start with proving this one. $$\text{Show that for any $n \geq 2$, $4^n > 3^n+2^n$}$$
3
votes
1answer
35 views

Where did this “+1” term come from for this inductive proof?

Where did this "+1" term come from for this inductive proof? It is in boxed in black. For context, We are trying to prove this sequence: has the following solution: $$x_{ n }=\frac { 3^{ n+1 ...
1
vote
1answer
28 views

Discrete Math Induction: $\sum^n_{i=1} \frac1{i(i+1)}$ [duplicate]

For $\sum^n_{i=1} \frac1{i(i+1)}$ Find a formula and proofs that it holds for all n ≥ 1. How would I find the formula for this one that can hold for all n ≥ 1?
-1
votes
2answers
40 views

Discrete Math On Induction proof: $\sum_{i=1}^n n2^n = (n-1)2^{n+1} + 2$ [duplicate]

Show by induction that the following formulas hold. $\sum_{i=1}^n n2ⁿ = (n-1)2^{n+1} + 2$ What did a similar problem to this but this one is a little different. I think is because this one has a ...
-1
votes
1answer
85 views

Use Mathematical Induction to prove that $\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} +…+\frac{1}{n(n+1)}=1-\frac{1}{n+1}$

Use Mathematical induction to prove that for all integers, $n$ is greater than or equal to $1$. I am confused on what to do after I do the the basis step that is using $n$ as $1$. $$\frac{1}{1 \cdot ...
0
votes
3answers
47 views

Prove that $\sum \frac{1}{2^n} = 1- \frac{1}{2^n}$ [closed]

Prove that $$\Large\sum\limits_{k=1}^n \frac{1}{2^k} = 1 - \frac{1}{2^n}$$ for all $n$. I am apparent not good enough at algebra for this one.
0
votes
2answers
19 views

Let $A_1, A_2, \ldots, A_n$ be sets (where $n \ge 2$). Suppose for any two sets $A_i$ and $A_j$ either $A_i \subseteq A_j$ or $A_j \subseteq A_i$

Let $A_1, A_2, \ldots, A_n$ be sets (where $n \ge 2$). Suppose for any two sets $A_i$ and $A_j$ either $A_i \subseteq A_j$ or $A_j \subseteq A_i$. Prove by induction that one of these $n$sets is a ...
1
vote
2answers
61 views

Prove by induction $1 + \frac{1}{2} + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{2^n} \ge 1 + \frac {n}{2}$

Prove by induction $1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \ldots + \frac{1}{2^n} \ge 1 + \frac {n}{2}$ I can't explain in words how the left hand side of the equation is achieved soI shall ...
1
vote
4answers
44 views

proof by induction: sum of binomial coefficients

Question: Prove that the sum of the binomial coefficients for the nth power of $(x + y)$ is $2^n$. i.e. the sum of the numbers in the $(n + 1)^{st}$ row of Pascal’s Triangle is $2^n$ i.e. prove ...
2
votes
1answer
49 views

Fibonacci proof by induction

I have fibonacci numbers defined as such: $$ f(n) = f(n-1) + f(n-2)$$with$$ f(0) = 0 $$$$f(1) = 1$$ I have to prove that $$ F(n) \geq 1.5^{n-1}, n \geq 6$$ Base Case: $$ f(6) = 8 \geq (1.5)^5 ...
0
votes
1answer
17 views

Prove that all elements in the set T is divisible by 3 using structural induction.

Let T be the set defined recursively as follows: (1) (0,3) $\in$ T (2) If (x, y) $\in$ T, then (x + 2, y - 1) $\in$ T and (x - 3, y) $\in$ T. (3) Every element of T can be obtained from (1) by ...
0
votes
2answers
49 views

Proving by mathematical induction

Let $d \in N $ be an odd integer. Prove by induction that: $\forall k \in N$ , $d^k$ = 1 (mod 2). How do I begin this question? I have a hard time understanding what to do for the inductive step. ...
1
vote
9answers
284 views

How to prove for each positive integer $n$, the sum of the first $n$ odd positive integers is $n^2$?

I'm new to induction so please bear with me. How can I prove using induction that, for each positive integer $n$, the sum of the first $n$ odd positive integers is $n^2$? I think $9$ can be an ...
0
votes
0answers
42 views

Prove $F_{n+2} \ge x^n$ by induction where $x = (1 + \sqrt{5})/2$

Base Case: $n = 1$: $F_3 \ge x^1$ translates to $3 \ge 1.6$, so the base case holds. Induction Hypothesis: Assume the statement is true for all $n$ such that 40 \le n \le k$. We will prove this ...
0
votes
0answers
27 views

How to use two types different forms of induction to prove stamp problem?

For this problem I have to prove using two different types of induction to show that using only 3 cent stamps and 5 cent stamps, any postage amount 8 cents or greater can be formed. Using the two ...
0
votes
0answers
33 views

Proving this property of a tournament graph by induction?

I am working on practicing proofs by induction. Can you please take a look at the proof below and tell me if I proved it correctly? I am particularly worried about the inductive step. Definition ...
0
votes
1answer
28 views

How can I prove prime factorization theorem by induction?

The prime factorization including both existence and uniqueness. I have totally no idea about this problem except the basecase. In this problem we only consider number greater or equal to 2. So the ...
1
vote
4answers
72 views

prove that a power of odd number is always odd by induction.

The problem has confused me for like half hour. An integer is odd if it can be written as d = 2m+1. Use induction to prove that the ${d^n}$ = 1 (mod 2) by induction, the basecase is pretty simple , ...
1
vote
5answers
115 views

How to prove that $n^5 - n$ is a multiple of $5$? [duplicate]

Hello I'm new to induction so please bare with me. For this problem I have to use induction to prove: For every integer $n\geq 1$, the number $n^5 − n$ is a multiple of $5$. Can someone please help me ...
1
vote
1answer
39 views

How would I solve this mathematical induction proof? I am stuck after the first part of the induction.

$$1 + 5 + 5^2 + \ldots + 5^n = \frac{5^{n+1}-1}{4}$$ Basis case $n= 0$: $1^0 = 1 \;\;\;\;\;\;\;\;\;\;\;\; \frac{5^{1+1}-1}{4}=1$ Assume true for $n=k$: $$1 + 5 + 5^2 + \ldots + 5^k = ...
3
votes
2answers
52 views

Help finishing proof via induction for a summation

So I have to prove the following equation using induction for n >= 2: $$ \sum\limits_{i=1}^n 4/5^i < 1 $$ However the question asks me to prove something stronger such as this: $$ ...
0
votes
2answers
40 views

What is the easiest way to prove by induction?

Is there any easy way to do this? I get the basic step.. where you prove it for some number.. but I don't get the induction step. Do you literally take the given equation that you just proved with ...
1
vote
0answers
106 views

Can I use Strong Induction to prove graph theory? - Hamilton Path/Tournament Graphs

I am working on the below proof. I am still new to proves so I am wondering if you guys can answer the following questions: 1) Did I use the inductive hypothesis correctly here? (By the inductive ...
-1
votes
0answers
14 views

Discrete Math Inductive Definition for Strings

Find an inductive definition for the following set of strings: $S = \{a^pbc^r : p\text{ is a natural number, and r is a natural number greater than }0\}$
0
votes
2answers
33 views

Induction for a sequence starting with a negative and ending with a positive number.

Prove by induction on n that for any $n \ge 2$, any sequence of non-zero real numbers $a_1, a_2, \dots, a_n$ that starts with a negative number (meaning $a_1 < 0$) and ends with a positive number ...
0
votes
1answer
34 views

Mathematical Induction Proof. Help with last step

I am to use mathematical induction to prove: $\sum_{i=1}^n$ $\frac{1}{i^2}$ $<$ $2 - \frac{1}{n}$ my base case is n = 3: $LHS: \frac{1}{1}+\frac{1}{4}+\frac{1}{9}= \frac{49}{36}$ $RHS: ...
2
votes
2answers
50 views

How to prove $n^3 < 4^n$ using induction? [duplicate]

It's true for all Natural numbers. What I've got so far: Prove $P(0) \to $ base case: Let $n = 0$ $(0)^3 < 4^0 = 0 < 1$ Then $P(0)$ is true. Part Two: Prove $P(n) \Rightarrow P(n + 1) ...
0
votes
0answers
24 views

Prove by induction about line set

A set of straight lines in the plane is said to be in general position if no two lines are parallel and no three lines intersect at a common point. Consider $n\geq3$ lines in general position in the ...
0
votes
2answers
48 views

Prove via induction this recursively defined sequence

Let $P(n) = 2P(n-1) + n, P(1) = 3.$ Use induction to show that $$P(n) = 3(2^n) - n - 2$$ Highly verbose solutions are greatly appreciated.
0
votes
3answers
59 views

Prove that $3+ 3\cdot5+…+3\cdot5^n = \frac{3(5^{n+1}-1)}{4}$ for all nonnegative integers.

I have been stuck on this one for a while. Supposed to use induction to prove that $3+ 3\cdot5+...+3\cdot5^n = \Large\frac{3(5^{n+1}-1)}{4}$ for all nonegative integers. I don't know if I'm taking ...
-1
votes
1answer
24 views

Prove by Induction (Geometric Progression)

Prove by induction that for any real number $q≠1$ and any $n\in \mathbb N$ we have $ \sum_{i=0}^n q^i=\frac{q^{n+1}-1}{q-1} $
3
votes
3answers
121 views

Prove that, for any positive integer n: $(a + b)^{n} \leq 2^{n-1}(a^{n}+b^{n})$

Prove that, for any positive integer n: $(a + b)^{n} \leq 2^{n-1}(a^{n}+b^{n}) $ I tried induction theorem, when $n = 1$ it is obviously right. But, say $n=k$, It does not make sense since I cannot ...
1
vote
2answers
43 views

How to prove this Mathematical Induction problem?

We got $n \geq 3$ lines drawn on a surface with conditions below: No two lines are parallel. No three lines make a conjunction in a specific point. Prove that one of the areas created by these ...
2
votes
0answers
52 views

How to prove this claim using Mathematical Induction?

We have $n$ points on a surface and for each $3$ points, we are able to put them into a circle with radius of unit length. Prove that all of these points are on circle with radius of unit length. My ...
1
vote
0answers
96 views

How to prove this equation using Mathematical Induction?

I was trying to prove this. I tried somehow but didn't get any idea. I think we can prove this using induction. I'd really appreciate it if you could help me. ...
0
votes
1answer
30 views

Question over regular induction: Let $P(n)$ be the statement that $n$-cent postage can be formed using just 4-cent and 7-cent stamps

Prove $P(n)$ is true for $n \geq 18$ using regular induction. I know how to do this problem using strong induction but don't know how to proceed using regular induction. I know the first step is ...
0
votes
2answers
62 views

Mathematical Induction

I've gotten to the final step and believe my problem lies within my algebra. Prove the following: $1 \times 3 + 2 \times 4 + 3 \times 5 + ... + N(N+2) = \frac{N(N+1)(2N+7)}6$ Here is my show that ...
1
vote
1answer
37 views

Question over induction, suppose $P(n)$ is true for all positive integers $n$ that is a power of 2.

Suppose, that $P(k+1) \Rightarrow P(k)$ for all positive integers $k$. How would I prove $P(n)$ is true? I am getting confused since this is going the 'other way'. Usually $P(k)\Rightarrow P(k+1)$
-5
votes
2answers
62 views

Question about induction, if $P(k)$ implies $P(k+3)$ [closed]

Suppose $P(1)$ and $P(2)$ are true. For what values of $n$, is $P(n)$ true for if for every positive integer $k$,if $P(k)$ is true then $P(k+3)$ is true?
0
votes
2answers
44 views

Proof by Mathematical Induction.

Using mathematical induction I am to prove: $ \left( \begin{array}{ccc} 1 & 1 \\ 1 & 0 \end{array} \right)^n $ = $ \left( \begin{array}{ccc} F_{n+1} & F_n \\ F_n & F_{n-1} ...
0
votes
3answers
43 views

Mathematical Induction Proof

I am to use mathematical induction to prove: $\sum_{i=1}^n$ $(i \times i!) = (n+1)! - 1$ my base case is n = 1 $RHS: (1 \times1!) = 1$ $LHS: (1+1)! - 1 = 1$ If I am not mistaken the next step is ...
0
votes
1answer
28 views

Solving proof by induction row

Hello i am not able to figure out how to continue on this induction. I did work so far: What to do after that? UPDATED: so far: is it right?? but what about k + 1 it doesnt hold for 2^k
0
votes
2answers
17 views

Proving inequalities by using induction

For all $n\ge 2$ prove $n^2 \ge n+1$ by using induction. Here is my attempt at the problem. Base case: $n=2$, $2^2 > 2+1$, $4>3$ Inductive step: $p(k) = k^2 \gt k+1$ $p(k+1)=(k+1)^2 \gt ...
0
votes
1answer
34 views

Prove divisibility by using induction

Prove that for integers $n > 0$, $n^3 + 5n$ is divisible by $6$. Here is what I have done: Base Step: $n=1$, $1^3+5(1)=6$ Inductive Step: $p(k)=k^3 + 5k =6m$, $m$ is some integer ...
1
vote
1answer
54 views

Prove $n! \geq n^2$ for $n \geq 4$

I am working through a discrete math course, and have come upon a question that I don't understand how the solution was obtained. The question is, prove $n! \geq n^2$ Hypothesis: $p(n): n! \geq n^2, ...
0
votes
2answers
28 views

Math Induction to prove recursion

This is a problem from a practice test. I don't understand how the answer was produced using math induction. And yes, math induction is required for this problem. Define a function f: $\mathbb{N}$ ...
0
votes
2answers
46 views

Proof by Induction - Sequence of integers

Suppose a sequence of integers $a_1$, $a_2$, ... is defined as: $$a_1 = 3$$ $$a_2 = 6$$ $$a_n = 5a_{n-1} - 6a_{n-2} + 2$$ for all $n\ge3$ $\mathbf {Prove}$ $\mathbf {S(n)}$: $a_n = 1 + 2^{n-1} + ...
0
votes
1answer
39 views

Prove that $n^2 < 2^n$ for all $n \geq 6$

My approach to solving this: By induction. (1) $S(n) = (n^2 < 2^n)$ for all $n \geq 6$, $n \in \mathbb N$. (2) Base Case: $n = 6$ $$6^2 < 2^6$$ $$36 < 64$$ So the statement is true for ...
1
vote
2answers
65 views

Strong Induction: Finding the Inductive Hypothesis

Consider this claim: Every positive integer greater than 29 can be written as a sum of a non-negative multiple of 8 and a non-negative multiple of 5. Assume you are in the inductive step and trying ...
-6
votes
2answers
168 views

Induction of $A_i$ [duplicate]

The base case $n=1$: $B\cup\left(\bigcap_{i=1}^1A_i\right)=B\cup A_1$ and $\bigcap_{i=1}^1(B\cup A_i)=B\cup A_1$. Now, suppose inductively that ...