0
votes
2answers
50 views

Mathematical Induction - Inequality

Does anyone have any idea on how to complete the inductive step? Thm: For all $n >= 0~~~~ 6^n + 4 > n^3$ Pf: by Induction     Let $P(n)$ be proposition that $~6^n + 4 ...
2
votes
1answer
68 views

Introductory Induction Proof

I am in currently in a discrete mathematics class, and I've done well on every problem I've encountered. Unfortunately, I find myself weak at some of the seemingly straight forward induction problems. ...
1
vote
1answer
26 views

Expanding Base 2B representation of an integer

Consider an integer$L$ written in Base 2B which digits $$a_n a_{n-1} a_{n-2} ... a_1 B$$ Where $a_i$ are arbitrary constants such that $9 \le a_i < 2B$. I am attempting to prove that the square ...
1
vote
2answers
53 views

If $a_i>o$ then $(a_1a_2\cdots a_{2^n})^{1/2^n}\leq \frac{a_1+a_2+\cdots+a_{2^n}}{2^n}$

I need help to prove this inequality, I have no idea how to proceed with the inductive step: $$a_1,a_2,\ldots,a_{2^n}>0 \Longrightarrow(a_1a_2\cdots a_{2^n})^{1/2^n}\leq ...
1
vote
1answer
31 views

Can someone explain the logic behind this step in a induction problem

There is a question in the book that I don't quite understand. Question Show that $n^2$ is smaller than $2^n$ whenever $n\ge5$. At the $k+1$ step it gets very whacked and confusing. $k+1$ ...
1
vote
1answer
39 views

Prove by Structural induction, circular permutations

Prove by Structural Induction: For a circular permutation of $n$ elements, the number of permutations is $(n-1)!$ How is this done?
0
votes
2answers
41 views

How do I reduce this induction problem at the k+1 step

Show that $2^n > n^2$ through induction and so far I got to the $k+1$ step, but I am stuck. I have $2^{k+1} = 2 +2^k$, but I don`t know how the book turned it into $k^2 +k^2$. The book then ...
3
votes
5answers
591 views

The sum of three consecutive cubes numbers produces 9 multiple

I want to prove that $n^3 + (n+1)^3 + (n+2)^3$ is always a $9$ multiple I used induction by the way. I reach this equation: $(n+1)^3 + (n+2)^3 + (n+3)^3$ But is a lot of time to calculate each ...
4
votes
2answers
34 views

Proving Induction $(1\cdot2\cdot3)+(2\cdot3\cdot4)+…+k(k+1)(k+2)=k(k+1)(k+2)(k+3)/4$

I need a little help with the algebra portion of the proof by induction. Here's what I have: Basis Step: $P(1)=1(1+1)(1+2)=6=1(1+1)(1+2)(1+3)/4=6$ - Proven Induction Step: ...
2
votes
6answers
260 views

Discrete math induction problem.

I am stuck at this step in the inductive process and I was wondering if someone can help me out from where I am stuck. Question: if $n$ is a positive integer, prove that, ...
0
votes
2answers
44 views

Induction inequality check

check my proof, I feel like I made a mistake :) so I'm looking to prove that when $p(n)$ is $n!<n^n$, $p(n)$ is true for all $n>1$. Base Case $$ p(2) \iff 2!<2^2 \iff 2<4 $$ Assume p(k) ...
2
votes
2answers
90 views

Proof by induction that $(1^3 + 2^3 + 3^3+\cdots+n^3) = (1 + 2 + \cdots + n)^2$

I'm sitting with the proof in front of me, but I do not understand it. $$A = \{n \in Z^{++} \mid (1^3 + 2^3 + 3^3+\cdots+n^3) = (1 + 2 + \cdots + n)^2\}$$ The first step of proof by induction is ...
-4
votes
1answer
49 views

Use mathematical induction to prove that the proposition is true [closed]

Use mathematical induction to prove that the proposition is true: $(x + 1)^n > 1 + x^n$; for $n\geq2$ and $x>0$;
1
vote
4answers
87 views

Determine which Fibonacci numbers are even

(a) Determine which Fibonacci numbers are even. Use a form of mathematical induction to prove your conjecture. (b) Determine which Fibonacci numbers are divisible by 3. Use a form of mathematical ...
1
vote
3answers
28 views

Question regarding Strong Principle of Induction

I'm currently studying Discrete mathematics from a book by Normal L. Biggs and i don't understand the thinking about an example on Strong Principle of Induction, The example i need help ...
2
votes
3answers
67 views

Induction: Prove that it is possible to seat people in a circle so that everyone sits beside a friend

Use induction to prove the following: If each person in a group of $n$ people is a friend of at least half the people in the group, then prove that it is possible to seat them in a circle so that ...
0
votes
2answers
35 views

Deducing formula for nth term in sequence and validate using principles of induction

I a working my way through some old exam papers but have come up with a problem. One question on sequences and induction goes: A sequence of integers $x_1, x_2,\cdots, x_k,\cdots$ is defind ...
0
votes
3answers
72 views

Prove that $n = 2a + 3b$.

How can I prove by induction that for any natural number $n$ there exists integers $a,b$ so that $2a+3b=n$ I can prove the base case, and I can imagine why it works but how can I prove it ...
0
votes
2answers
32 views

Using induction to prove an equation

Use induction to show that $n(n + 1) < 2^n$ for all $n \ge 5$. Assuming is true for $n = 5$, $5(6) < 2^5$ is true. How can I prove this using induction?
1
vote
2answers
84 views

Use the recursive definition of summation together with mathematical induction to prove a sequence

Use the recursive definition of summation together with mathematical induction to prove that for all positive integers $n$ if $a_1, a_2,\ldots, a_n$ are real numbers, then $$\sum_{k=1}^n(3a_k - 2k + ...
-2
votes
1answer
54 views

Prove by indution [on hold]

Can someone help me with this homework question. Prove the following by induction $$\sum_{k = 1}^n k {n \choose k} = n \cdot 2^{n - 1}.$$ Thanks
1
vote
2answers
103 views

Find an explicit formula for the recursive sequence (tips?)

Problem: A sequence is defined recursively as follows: Sk = 2k - Sk - 1, for all integers k greater than or equal to 1 S0 = 1 Use iteration to guess the explicit formula for the sequence. Use ...
1
vote
3answers
77 views

Use mathematical induction to prove that $(3^n+7^n)-2$ is divisible by 8 for all non-negative integers.

Base step: $3^0 + 7^0 - 2 = 0$ and $8|0$ Suppose that $8|f(n)$, let's say $f(n)= (3^n+7^n)-2= 8k$ Then $f(n+1) = (3^{n+1}+7^{n+1})-2$ $(3*3^{n}+7*7^{n})-2$ This is the part I get stuck. Any help ...
0
votes
1answer
44 views

Prove by Induction that: $1+nx\le (1+x)^n$?

$1+nx\le (1+x)^n$, for all real numbers $x>-1$ and integers $n\ge 2$. Can you please also explain a little of the basic step and the inductions step. Thank you in advance.
0
votes
0answers
57 views

Variation of Nim: Player who takes last match loses

Here is a homework problem I can't understand the solution to. Can anyone help me understand why they are using "mod 4"? Can someone help me understand this strong induction example? Thanks everyone! ...
0
votes
1answer
48 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
37 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
29 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
49 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
91 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
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
71 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
113 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
60 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
18 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
3answers
62 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. ...
0
votes
9answers
451 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
44 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
41 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
39 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
108 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
129 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
44 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
59 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
47 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
215 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 ...
0
votes
2answers
36 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
37 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
54 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) ...