0
votes
2answers
29 views

Proof by induction sum $2^j = 2^{n+1} - 1$

I am trying to solve a previous test for an exam, and there are no solutions. The problem I am trying to solve is If $n$ is a natural number, then $1 + 2 + 2^2 + 2+3 + ... + 2^n = 2^{n+1} -1$ ...
0
votes
3answers
56 views

Induction, show that something is smaller then …

I have to show the following by induction. $1 \cdot 2 \cdot 3 ... (n - 1) \leq (\frac{n}{2})^{n -1}$ As it is homework I "only" need a push in the right direction. my thought is that is something ...
1
vote
4answers
45 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 ...
0
votes
1answer
26 views

Inductive Proof Recursive Definition

Using this recursive Definition: $$a_{n} = \left\{\begin{matrix} 4 & n=1\\ a_{n-1}+4n-5 & n \geq 2 \end{matrix}\right.$$ I somehow have to prove using induction $$a_{n} = 2n^{2} - ...
0
votes
1answer
35 views

Fibonacci Proof with Induction [duplicate]

$$f(n) = \left\{\begin{matrix} 0 & n=1\\ 1 & n=2\\ f_{n-1} + f_{n-2} & n\geqslant 2\end{matrix}\right.$$ How can I prove by induction that $$f_{n} \geq \left ( 1.5 \right )^{n-1}$$ ...
2
votes
2answers
45 views

Fibonacci Proof Using Induction

$$f(n) = \left\{\begin{matrix} 0 & n=1\\ 1 & n=2\\ f_{n-1} + f_{n-2} & n\geqslant 2\end{matrix}\right.$$ How can I prove by induction that $$f_{n} \leq \left ( \frac{1+\sqrt{5}}{2} ...
0
votes
3answers
32 views

Divisibility proof by induction.

$ 169$ | $3^{3n+3}-26n-27$ ? Fulfilled for $n=0$. Induction to $n+1$: An integer $x$ exists so that $ 169x= 3^{3n+6}-26n-27-26$ $ 169x= 27*3^{3n+3}-26n-27-26$ $ 169x= 26*3^{3n+3}+3^{3n+3}-26n-27-26$ ...
0
votes
3answers
31 views

Induction summation proof

Don't want a full answer but can somebody help me in the right direction with this problem. Have to prove using induction $$\forall n \geqslant 2: \sum_{i=1}^{n} \frac{4}{5^{i}} < 1$$
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 = ...
1
vote
1answer
55 views

Proof by induction: $2^n > n$

Base is $2^1 > 1$. Now we assume $2^n > n$ and try to obtain $2^{n+1} > (n+1)$. If I can use $2^n > 1$, I could just add that to $2^n > n$ and get $2^{n+1} > (n+1)$ but I don't ...
1
vote
0answers
110 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
1answer
31 views

Help with multiple statement induction proof

I am learning proof by induction in my math class and I am having trouble with this problem: Prove that for $k \in N, 3^{4k-3}\equiv 3 \pmod{10}, 3^{4k-2} \equiv 9 \pmod{10}, 3^{4k-1} \equiv 7 ...
0
votes
5answers
100 views

Help with proof using induction: $1 + \frac{1}{4} + \frac{1}{9}+\cdots+\frac{1}{n^2}\leq 2-\frac{1}{n}$

I am having trouble with the following proof: For every positive integer $n$: $$1 + \frac{1}{4} + \frac{1}{9}+\cdots+\frac{1}{n^2}\leq 2-\frac{1}{n}$$ My work: I have tried to add ...
0
votes
1answer
75 views

[Beginner]How to tackle mathematical proofs?

So I recently joined university for a BSc in mathematics. I have never been exposed proofs but I have knowledge of algebra, trigonometry, and some differentiation/integration. Now I'm struggling with ...
1
vote
1answer
69 views

Is This a Proof by Induction?

Prove, disprove, or give a counterexample: $$\sum_{i=0}^n \left(\frac 3 2 \right)^i = 2\left(\frac 3 2 \right)^{n+1} -2.$$ I went about this as a proof by induction. I did the base case and ...
2
votes
1answer
128 views

Proving that $\,\sqrt [n] n < 1 + \sqrt{\frac{2}{n}}\,$ for all positive $n$

Hello I am having difficulty proving the following inequality: $$ \sqrt[n]{n} < 1 + \sqrt{\frac{2}{n}} \quad \text{for all positive integers}\,\,\, n. $$ I am trying to use mathematical induction ...
0
votes
2answers
54 views

Using induction to prove $2^{n-1}(1 + a_1a_2\ldots a_n) \geq (1+a_1)(1+a_2)\ldots(1+a_n)$ for $a_i \geq 1$

Hello I have been blasting at this inequality proof and it is just not doing what I want it to do: Prove that $2^{n-1}(a_1a_2\ldots a_n + 1) \geq (1+a_1)(1+a_2)\ldots(1+a_n)$ assuming that ...
2
votes
1answer
31 views

Inductive proof of an inequality

I am trying to prove this inequality by induction: For all $x$ in the interval $x\in [0, \pi]$, prove that: $$ |\sin (nx)| \leq n\sin(x) \textit{, n a nonnegative integer}$$ The base case is ...
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) ...
2
votes
3answers
83 views

is it wrong to do this to solve an induction question

When doing an induction problem is it wrong to simply add the next variable to both sides? for example for all natural numbers $$4+9+14+19....+(5n-1)=\frac{n}{2}(3+5n)$$ assume true for k ...
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
4answers
57 views

prove by induction: $3 + 5 + 7 + … + (2n+1) = n(n+2)$

Use the principle of mathematical induction to prove that $$3 + 5 + 7 + ... + (2n+1) = n(n+2)$$ for all n in $\mathbb N$. I have a problem with induction. If anyone can give me a little insight ...
0
votes
1answer
22 views

Proving by induction propositions of the type $P(n_1, n_2, …, n_k)$, where $n_1, n_2, …,$ and $n_k$ are natural numbers

For example: I've seen proofs of the multinomial theorem that use induction in the number of terms that are elevated at some power, but none that use induction in the exponent instead of using it in ...
1
vote
2answers
37 views

Proving a summation involving binomial coefficients.

I need to prove the following inductively: (http://upload.wikimedia.org/math/9/e/5/9e57871ba17c1ad48e01beb7e1bb3bb9.png) $$\sum_{i=1}^{n} i{n \choose i} = n2^{n-1}$$ And for the life of me I can't ...
0
votes
0answers
27 views

Validity of a proof by induction

By intuition, I would say that if L1 is a subset of L and that L is regular, then L1 is also regular, because L1 has less states than L2 and therefore there must be an automata for L1 too. However, ...
0
votes
2answers
82 views

Proving that $fib(n) < (5/3)^n$ for $n \ge 1$ by induction

I know this has been shown before here but no post really answered my question. I had this problem given to me as an induction practice problem and I couldn't solve it without help. When I got the ...
3
votes
2answers
172 views

Fallacious Induction Proof that All Integers are Equal [duplicate]

We're currently learning about induction in my real analysis course. I came up with the following proof that is obviously false but cannot quite figure out why it fails. Here it is... "Any set $S$ of ...
2
votes
1answer
68 views

Prove by induction that $2^{2n} – 1$ is divisible by $3$ whenever n is a positive integer.

I am confused as to how to solve this question. For the Base case $n=1$, $(2^{2(1)} - 1)\,/\, 3 = 1$, base case holds My induction hypothesis is: Assume $2^{2k} -1$ is divisible by $3$ when $k$ is a ...
1
vote
2answers
63 views

What is wrong with the proof given below?

This problem comes from Solow's book, 2nd edition. What is wrong with the proof given below? If $r$ is a real number with $|r| \leq 1$, then for all integers $n \geq 1, 1 + r + r^2 + \ldots + ...
2
votes
4answers
125 views

Proof that $x^k < k^x$

So, I want to prove that $x^k$ is less than $k^x$ for any $x > k$. $x$ and $k$ are both integers. My first approach was an induction over $k$, given that the numbers are integers. I also ...
1
vote
2answers
53 views

Induction proof equivalence

In Induction, we do the following: Check $P(1)$ is true, then show that if $P(k)$ is true, then $P(k+1)$ is also true. So we proceed to assuming $P(k)$ is true, then attempt to show $P(k+1)$ is true, ...
1
vote
2answers
60 views

How to prove $\sum_{k\leq n}^{n} \binom{n}{k}= 2^n$ by induction [duplicate]

$\sum_{k\leq n}^{n} \binom{n}{k}= 2^n , n, k \in \mathbb{N}$ Im trying with mathematical induction but im stuck. My inductive step: $H) \sum_{k=0}^{h} \binom{h}{k}= 2^h$ $T) \sum_{k=0}^{h+1} ...
0
votes
1answer
64 views

How do i prove $\text{F}_\text{n+1}^2 - F_n\text{F}_\text{n+2} = (-1)^n$ by induction? [duplicate]

$F_n$ refers to the $n$ term of the Fibonacci Sequence. I think i'm suppose to prove this by induction. I already have the base case. I am at: $\text{F}_\text{k+1}^2 - F_k\text{F}_\text{k+2} + ...
-1
votes
1answer
42 views

Proof by induction and divisibility $21 | (4^{n+1} + 5^{2n-1}) $ [duplicate]

Prove by induction: $21 | (4^{n+1} + 5^{2n-1}) $ Skipping through the basis and onto the induction: $4\cdot 4^{n+1}+5^2 \cdot 5^{2n-1}=21a $ for some integer $a$ The following steps were: ...
2
votes
5answers
50 views

Divisibility induction proof

I'm stuck on the following proof by induction: $$8\mid3^n +7^n -2$$ And this is how far I've gotten: $$3\cdot3^n+7\cdot7^n-2\\3(3^n+7^n-2)+7^n(7-3)-2$$ Any help on where to go after this would be ...
0
votes
1answer
27 views

Advice for proving with induction scenarios with multiple chances for using the hypothesis.

I have done many, many questions about solving induction exercises. I managed to grasp a basic strategy: write all the information, take the statement you want to prove, try to apply the hypothesis ...
1
vote
1answer
47 views

Finding the explicit formula for the succession $x_0=2, x_{n+1} = 5x_n$ and proving it with induction

I'm trying to learn about recursion, first with this exercise: Find the explicit formula for the succession $$x_0=2, x_{n+1} = 5x_n$$ So, from what I've seen, I should test a bit. I see that the ...
1
vote
2answers
41 views

Proving by induction inequalities that lack the variable on the right side.

Doing proof by induction exercises with inequalities, I got stuck on one that is a bit different from the others. There is no $n$ term on the rightmost part of the inequality: Prove that the ...
2
votes
2answers
82 views

Proving by induction that $1+\frac{1}{2}+\frac{1}{3}+…+\frac{1}{n}\le\frac{n}{2}+1$ holds for all $n \ge 1$

While looking at some examples of proof by induction related to inequalities, I had this one that I didn't quite get: Prove by induction that the following holds for all $n \ge 1$: ...
0
votes
2answers
41 views

Strong induction proof with polygon

How can we show that if a simple polygon with at least four sides is triangu-lated, then at least two of the triangles in the triangulation have two sides that border the exterior of the polygon using ...
3
votes
2answers
63 views

Proof related with mathematical induction

I tried to prove this claim using mathematical induction. $ a^2 + 15a + 5 ≤ 21 a^2 $ $\;\; ∀a∈\mathbb Z^+$ The way is as the following: Basis: for a = 1 is true since 21 = 21 Inductive step: If ...
3
votes
0answers
49 views

Induction on Primitive Recursive Function

The set $F_{n}$ of primitive recursive function symbols of arity $n$ can be defined inductively as: \begin{align} & Z, \text{Succ} \in F_{1} & \\ &\pi_{j}^{n} \in F_{n} \quad \text{for ...
1
vote
5answers
72 views

An issue of understanding the inductive step in proof by induction

Induction step: We assume that P(k) is true and then we need to show that P(k+1) is true as well. If k is arbitrary and we assume it's correct, then how come one can't say, j = (k+1) and assume ...
3
votes
1answer
67 views

Prove that $x^n+x^{-n} \in \mathbf{N}$ if $x+\frac1x \in \mathbf{N}$

Assume that $x+\frac1x \in \mathbf{N}$. Prove by induction that $$x^2+\frac1{x^2}, x^3+\frac1{x^3}, \dots , x^n+\frac1{x^n}$$ is also a member of $\mathbf{N}$. I have my base, it is indeed true for ...
0
votes
1answer
46 views

Proof by induction; simplify when adding k+1th term. Understanding induction.

I want to prove: $$(-\frac{1}{2})^0 + (-\frac{1}{2})^1 + \cdots + (-\frac{1}{2})^k + (-\frac{1}{2})^{k+1} = \frac{2^{k+1}+(-1^k)}{3\cdot2^k} + (-\frac{1}{2})^{k+1}$$ How do I simplify the last bit, ...
1
vote
1answer
110 views

Prove a summation inequality by induction

I was having trouble proving by induction with this problem. $$\sum_{i=1}^n \frac{3}{4^i} < 1$$ for all $n \geq 2$ I went to see my professor and he said try proving this equality ...
2
votes
1answer
71 views

Use induction on $n$ to prove that $2n+1<2^n$ for all integers $n≥3$.

Use induction on n to prove that $2n+1<2^n$ for all integers $n\geq 3$. My attempt: Let $P(n)$ be the statement $2n+1<2^n$. Base case: Prove that $P(3)$ is true. $LS = 2(3)+1=7$ and ...
0
votes
2answers
52 views

Using induction to prove $a_n >2^n$

For the sequence $a_n=2a_{n-1}+1$ where $a_0=1$ Show that $a_n>2^n$ using induction. Use proof by contradiction (minimum counterexample). Attempt: 1. I assume, that ...
2
votes
1answer
36 views

Proof by induction for divisibility

I have to proof that $(a^n-1)$ is divisible by $(a-1)$ where $a \in \mathbb {N_{>1}}$ I think that I have the proof but I am not sure if that is the correct format. Induction hypothesis: ...
1
vote
1answer
33 views

Induction Proofs

C1 = 0, Cn = 4C$\lfloor n/2 \rfloor + n$ Prove that $Cn$ less than or equal to $4(n - 1)^2$ What I did: Base step: n = 1 $C1$ <= $4(1 - 1)^2$ 0 <= 0 therefore true how do you do the ...